After exploring Clock Town, you can reach the swamp from South Clock Town. The exit is across from the doors of the Clock Tower. Just talk to the guard while you are in human form and the guard will allow you to pass.
Go to the Swamp
In Termina Field you will find Chuchus, which are slimy enemies that have an item inside. If you kill a ChuChu, another one will appear after a while.
Go south through a hollow log, then approach the tree that has white markings on the bottom. You will see a cut scene where Tatl and Tael meet the Skull Kid, whose friends abandoned him because he played too many pranks. Some time later, the Skull Kid knocked out the Mask Salesman and stole Majora's Mask.
Go to the left of the tree and continue going south. You reach the Southern Swamp.
From where you enter the swamp, go to the right and hit the owl statue to activate it.
You can't go very far into the swamp because there is poisonous water almost everywhere. If you climb the ladder and go into the house, which is the Swamp Tourist Information Center. You find out that you can get a boat cruise, but the cruise ticket counter is closed. You are told to inquire at the Magic Hags' Potion Shop near the edge of the swamp.
From the Tourist Information Center, swim east (where the lilypads are) to find a dock. Go onto the grass there. You see an archway and a big potion cauldron. Go through the arch, then make your way along the path past the Deku Babas.
If you go up the ladder of the tree at the end of the path and go into the Potion Shop, you can talk to Kotake, who is there selling potions. She says her sister Koume, who runs the boat cruise ticket counter, went to the woods out back looking for mushrooms. Koume is late, though, so Kotake asks you to go look for her. You can shop for potions before you leave. Right now she only sells red and green potions. If you speak to Kotake again, she will ask for fragrant mushrooms.
Go outside and go into the dark path behind the potion shop. Talk to the monkey and then follow it. Be careful of the Snapper turtles that attack along the way. If you follow the correct path (left, right, right, straight, left, and left), you will find Koume lying on the ground. Talk to her a couple of times and she will say that the Skull Kid hit her from behind and now she can't get up. She asks for something that will give her energy.
Go back to the potion shop and talk to Kotake. When she hears what happened to Koume, she gives you a red potion. Go back to the forest and find Koume again. The path is left, right, right, straight, left, and left. Talk to her and give her the potion. She will fly back to the boat cruise place. You will keep the empty bottle that the potion was in.
Go on a Boat Cruise
Leave the forest. Three monkeys will come up to you. Talk to them. They tell you that the monkey's brother was caught entering the Deku Temple above the waterfall and is being held in the Deku Palace. The monkey asks for your help.
Go back to the Tourist Information Center and talk to Koume in the ticket counter. She gives you a free Pictograph Box and a free boat cruise. You can take a picture with the pictograph box and enter the contest with it by giving the pictograph to the guy in the tourist information center after. Try taking pictures of unusual things. Whenever you give the guy a pictograph, you might get rupees depending on how rare the picture is. You can take a picture of Tingle and give it to the guy to get a Piece of Heart.
During the boat cruise, you will encounter a big Octorok in the water. The boat will hit the Octorok, getting rid of it. Then the boat will stop at the Deku palace. You can disembark if you are ready to enter the palace. However, if you choose not to disembark, the boat will continue its cruise, returning to the swamp.
Disembark at the palace and follow the monkey inside. When inside, put on the Deku Mask and cross the bridges to reach the two Deku Scrub guards. Talk to them and they will let you enter the palace. Go straight down the hallway to reach the king's chamber.
In the king's chamber, you can take a picture of the Deku King and give it to the pictograph guy to get either a Piece of Heart or 100 rupees if he already gave you a Piece of Heart. If you talk to the Deku King and the other Dekus, you find out that the Deku Princess is missing. The Dekus believe that the monkey kidnapped her, but the monkey says that a monster kidnapped her.
Leave the king's chamber, and the monkey's brother will hop down. Talk to him. He says that there is a secret route to the monkey's cage from the Outer Garden entrance, but the entrance is in a tall place, so you have to get a bean from the bean seller, who lives beneath the palace garden.
Reach the Bean Seller
The next step is to go into the Inner Palace Garden. There are two doors to this garden inside of the Deku Palace, just outside of the door to the king's chamber. If you go into the door to the right of the King's chamber's door (if you are facing away from the King's room), follow the path while avoiding the scrubs and you will find a Piece of Heart at the end.
Go into the door to the left of the king's chamber and avoid the scrubs there. At the end, you find a hole. Fall in and look around for the ramp in this underground area. Go up it to find the bean seller. He gives you a free bean, and then you can buy more for 10 rupees each.
You don't need to plant the bean down here. You can put a bug into the soft soil here to get rupees. Otherwise, be sure to use a bottle to scoop up some water before you leave.
Reach the Monkey's Brother
Step into the light to leave the underground area. Go out and get caught by the guards. Then, when outside of the palace, turn to face the front of the palace and then go around the right side of the palace. Plant a bean sprout there. Use the water from the bean seller's lair to make the bean sprout grow. Then walk onto the sprout. Ride it up to an opening in the wall. Go in.
You will be back in the inner garden. This time you land on top of a flower. Use the flowers to float from platform to platform. You will have to float past some scrubs that spit deku nuts at you. Make your way to a door in the wall. Walk across the bridge, then continue making your way to each moving flower platform. The final platform will rise up to the level of a high platform on the wall. Float to this high platform and go into the door there.
Go down to the lower area to find the monkey. Transform into your human form and talk to the monkey. He will ask you to cut his ropes. Hit the wooden pole that he's tied to with your sword and he will realize that it won't work. Then he asks you to show him a loud instrument. Transform into the Deku Scrub and use the ocarina. The monkey will teach you the melody that opens the temple. It's the Sonata of Awakening. Later, the monkey tells you to hurry to the temple using the shortcut that the Deku people use.
The shortcut is just outside of the Deku Palace. It's a flower that is near the wall. Get in the flower and float up to the top. Enter the cave. You will be on top of a large mushroom/flower thing. There are small Deku Flowers on top of each one. Float from flower to flower to reach a platform. You will find the owl, Kaepora Gaebora, on that platform. He mentions the owl statues, and he says to learn the song that is engraved on the stone that he is standing on. After he flies away, check on the stone. You will learn the Song of Soaring. It allows you to instantly warp to any stone owl statue that you have hit with your sword.
Use the Deku Flower on this ledge to fly across the gap next to the waterfall. Go into the door there to enter Woodfall.
Turn into a Deku Scrub and hop to the lilypad to the right. From there, hop to the stump just beyond. You will need to get past the Hiploops on the wooden bridge. Just hit them before they charge at you. Then at the top you can kill the Mad Deku Scrub to make a Deku Flower appear. Become a Deku Scrub and use the flower to float across to another Mad Deku Scrub. Carefully land and then kill the Mad Deku Scrub at the far end to make another Deku Flower. Float from that flower to the large platform across the way.
Transform back into human form and hit the owl statue to activate it. This will allow you to warp back here at any time using the Song of Soaring.
To have as much time as possible to finish the dungeon, use the Song of Time now to go back to the Dawn of the First Day (you may wish to use the Song of Soaring to return to Clock Town and deposit your rupees in the Clock Town Bank in West Clock Town first), then when you have returned to the Dawn of the First Day, use the Song of Inverted Time to slow the flow of time, then use the Song of Soaring to warp back to Woodfall Temple. When you slow the flow of time, you will have about three hours (in the real world) from the Dawn of the First Day until the moon crashes at the end of the Final Day.
When you are ready to enter the dungeon, stand on the Deku Symbol and transform into a Deku Scrub, then play the Sonata of Awakening as a Deku Scrub while standing on the Deku symbol. The temple will emerge from the water. Use the flower as a Deku Scrub to float to the temple. When you are ready, go into Woodfall Temple.