Deku Palace
Another monkey is waiting for you. He says that the water of the swamp has been poisoned lately and that his brother was captured in a palace by a Deku. Put on your Deku Mask and go ahead. Talk to the Deku scrubs and go straight on to the Royal Chamber. Speak to the king, who says the monkey has kidnapped the Deku Princess and insulted the Royal Family. Take a picture of him using the Pictograph Box, then talk to the monkey in the cage on the left. Leave this room, talk the other monkey who says that there's a secret route to the cage but you need beans to get there.
Go for the right Inner Palace Garden (to the right on the map). While avoiding guards, move to the second part of the garden and look for a hole. Drop through it and speak to the bean salesman. He says that you can get to the Outer Garden from over by the fountain and gives you a free Magic Bean sample. Remove your mask, take some Spring Water in your bottle, then plant the bean in the soft soil nearby (the soil is lighter). Water the bean with the Spring Water and get on the bean which allows you to reach a chest. Take some more Spring Water, go back to the salesman and buy another Magic Bean from him for 10 rupees. Cross the pond and enter the light to leave. If you want to, don't leave right away, get into the left Inner Palace Garden and pick up a Piece of Heart in the northwest corner.
Once in the Outdoor Garden, plant the bean and water it (not necessary if it is raining). Step on it and go through both inner gardens from platform to platform while using Deku flowers and shooting bubbles on Deku scrubs. If you fall, you will have to get back to the bean and start all over again.
Once in the monkey cage, take off your mask and talk to him. Hit the pillar to try to cut the rope, then as Deku Link, target the monkey and use your "ocarina". The monkey says that the princess is locked away in the Woodfall Temple and he teaches you the Sonata of Awakening. After being thrown out of the palace, go east, jump on the platform and take the pathway towards Woodfall. Before getting there, you can ride the boat in order to give your picture to the man from the Tourist Centre and be rewarded with a Piece of Heart (the contest will last until you clear the first temple).
Woodfall
Destroy both flying enemies, then use the Deku flowers to go south on a large rock, then again to go east near a waterfall, and go on.
N64 : Listen to the owl on the first platform, then look at the notes carved in the stone to learn the Song of Soaring which lets you travel from one Owl Statue to another. Next, move to the other platform and follow the passage.
Use the flowers and planks on your right to go south (shot two bubbles at each Hiploop in order to defeat them). Check the Owl Statue, then as Deku Link, step on the mark on the middle of the platform, play the Sonata of Awakening and the temple will appear. There is a Piece of Heart at the end of a plank in the northeast part of this area, which you can get now or later. And there is a Fairy Fountain in the west part but it's not very interesting to go now. Fly towards the temple and get in.