The Legend of Zelda: Majora's Mask/Southern Swamp
Your next location to visit is the swamp, which is to the south of Clock Town.
To get there, go to South Clock Town and speak with the guard. As you're now a human, he will let you out after noticing your sword.
 To the Southern Swamp
You'll now be in Termina Field, which serves as some sort of hub between the different areas of the game. There is one different area in each compass direction, as well as Clock Town in the very center. Termina Field is filled with rows of bushes guarded by Chu-Chus, which are easy to defeat and yield hearts or magic depending on their color.
For now, simply go to the south. As you pass by a tree with a Skull Kid drawing on it, Tatl will remember the story on how she met Skull Kid and how they had fun together. Once the story is done, continue to the south.
In this area, you can find Tingle again. Simply shoot a bubble to burst his balloon and you'll be able to buy a map of Woodfall for 20 Rupees, which is highly recommended. Once you're done, continue forward.
You're now in the Southern Swamp. Check the right to activate the Owl Statue there. The building at the center is the Swamp Tourist Center, but you cannot do anything in there at the moment so just ignore it for now.
 Helping Koume
Since the Big Octorok blocks your path forward, go to the left. Follow the passageway you see towards the big cauldron in the distance. For now pass it and enter the path behind it.
These are the Woods of Mystery. You'll need to find the correct path to reach the end, otherwise you'll just be returned outside. Helpfully, there's a monkey who will guide you through if you speak to him, so just follow him all the way to the end to find an injured old hag.
Her name's Koume, and she begs you to give her something to heal her. However, you do not have anything like that with you, so she tells you to return to the Magic Hag's Potion Shop which is the big cauldron you passed previously. Leave the woods via any of the exits, and climb the ladder to enter the Potion Shop. Speak with Kotake at the counter and as she finds out her sister is injured, she'll give you a Bottle with a Red Potion to help her. Do not even think about using it yourself, as this means you'll have to buy another one at your expense.
Now go back to the Woods of Mystery and follow the path you went through previously. Speak with Koume again and once she asks for it, give her the Bottle with the Red Potion inside. This will heal her right up again, and she'll zip away.
 To the Deku Palace
Exit the Woods of Mystery and return to the Swamp Tourist Center. Koume is now sitting at the booth and, because you helped her previously, she'll offer you a free boat cruise, and give you the Pictograph Box. This allows you to take pictures and show them to people. The boat cruise will lead right through the Big Octorok and to the Deku Palace. Be sure to get off when asked. The swamp here is poisoned so do not enter the water under any circumstances. Instead, follow the monkey through the passageway.
You're now at the Deku Palace. Put on the Deku Mask to transform into a Deku, and speak with the guards, who'll let you through. If you go through to the King's Chamber as they tell you, you'll find out that the monkey has been accused of taking away the princess. Get back out, and a monkey will tell you that a Magic Bean can lead you to the captured monkey. From here, enter the east side of the palace gardens. There are guards all across the area who will throw you out if you let yourself get caught by them. You need to sneak past to make it to the end. (This is easier at night because the guards' sight range will be indicated by dots.)
If you made it through you'll find a hole at the end. Fall down to find the Bean Seller, who will offer to sell you Magic Beans. Buy at the very least one, and be sure to get to the corner and use your bottle to catch some Spring Water. Once you're done here, exit the hole and let yourself be caught by the guards to return back outside.
As a Deku, follow the lilypads to the east. Here you'll find a soft spot of soil, which is where you'll want to plant your Magic Bean. Once done, pour some Spring Water over it and it'll grow. (Alternatively, wait until the Second Day, when a rainfall will make the sprout grow as well.) Use the Magic Bean to get up to a ledge. This leads to the top part of the palace gardens. Here you'll need to fly from platform to platform using the provided Deku Flowers, which is made difficult by some Mad Scrubs as well as the fact the platforms move back and forth. If you fall down you'll be thrown out again. At the end, enter the passageway to end up inside the monkey's cage.
You can speak with the monkey and he will assure you that he's not at fault for the princess' disappearance. What you'll want to do is transform to a Deku and use the Ocarina, which will make him teach you a new song, the Sonata of Awakening:
After learning the song, you are promptly thrown out. The monkey tells you to take the shortcut to Woodfall as you are carried out of the palace.
 To Woodfall
From the Deku Palace entrance, go to the east again, but this time, when you see a passageway to your right go there and use the Deku Flower to launch yourself up to it. Outside, use the Deku Flowers to fly from flower to flower (you'll probably want to take out the enemies first so they don't hit you in mid-air). At the end you'll meet the owl. After a short speech, read the tablet he stood on to learn the Song of Soaring:
Continue by using the Deku Flower to fly across the waterfall to the other side. Enter the passageway here to get to Woodfall. The passages are guarded by Hiploops, which can be killed with your bubbles. Follow the passageway and you'll end up on a platform with an Owl Statue (be sure to hit it with your sword), and a Deku ensign. As a Deku, stand on the ensign and play the Sonata of Awakening to make Woodfall Temple emerge from the water. Use the Deku Flower to fly across and enter it.