You begin in the Velvet Room, where you're talking to Elizabeth. After some conversation, you'll get to name the protagonist of Persona 4, so pick whatever you want and the game will begin. Watch the following cutscene, where you're introduced to the characters from Persona 3, and after some more scenes, you'll appear in a school.
After everyone goes to investigate the surroundings, they regroup and find out they're trapped there. Fuuka senses some Shadows and everyone gathers in front of the display where she senses them. Before you go in, though, two mysterious people show up and warn you not to enter. These are Zen and Rei, who appear to be students at the school and they have lost their memories.
They want you to take them with your party into the dungeon, and your initial party will be yourself, Akihiko, Shinjiro, Zen/Rei (they are one unit) and Mitsuru. Choose to go into the labyrinth and once you're inside, go straight and through the door. Turn right and follow that path until you're forced into a battle against three Lying Hableries, who are weak again Bash, Fire, Elec and Light.
The path so far is pretty linear and you can't get lost, so keep going until you come to another door. Go through it and you'll be in another room with a door, but everyone decides to head back for now, so you'll have to backtrack to where you entered the labyrinth. On the way, you'll be forced into another battle with two Lying Hablerie and a Cowardly Maya.
You already know the former's weaknesses, and the Maya is weak to all four elements and darkness. These Shadows will drop an item, a Shadow Piece, so keep going and exit the place. Back at the school, you head to a workshop to see about new equipment, with Theo offering to lend his assistance. You hand him the Shadow Piece you picked up, which he uses to make a Goho-M and a Short Blade.
The former is a very important item when exploring the dungeons, as you can use it when not in battle to return to the school at any time. This workshop also doubles as a storage for your items, should you ever find yourself carrying too much. Elizabeth will bring you to the Nurse's Office next, where you can rest from your battle wounds. After finishing up there, you get to reconsider your formation, so choose whoever you want to place in your party. Skip ahead to You in Wonderland Ch. 1 to get started.
Unless there are any major changes, going through the dungeons themselves is largely the same for both the Persona 4 Hero and the Persona 3 Hero, so you should be able to follow anything after this no matter which you chose at the beginning of the game.
Of course, the biggest different between the two, until you clear You in Wonderland, will be the conversations that happen, but everything else, especially in regards to monsters and events that happen within the labyrinths are the same.