The Great Deku Tree tells Navi to find you... after you see firsthand Princess Zeldas Nightmare! With a Fairy, go to where the map to the right says to go. The Kokiri Sword! Explore in the grass, Midos house, etc. to get 40 rupees. Go to the shop to buy a Deku Shield. Go to where Mido is and he will let you through. After the talk ahead, enter Inside the Deku Tree.
INSIDE THE GREAT DEKU TREE
Go up and around to go up the side of the dungeon. To jump, just walk towards it, and don't stop. YOU GOT THE DUNGEON MAP! To open a chest, walk towards it and press the A button.
Continue going up the steps. Do NOT climb the wall. Those are Skullwalltulas and they bite... really, bite! Go to the Door and enter by pressing A. Inside is a Deku Scrub. Use your Deku Shield to reflect back his attacks by Z-Targeting and having your shield out. You're his master now. He leaves a Heart and you can move onward. Jump across to the chest, and quick because the floating platform will collapse. YOU GOT A FAIRY SLINGSHOT! Now use it, by aiming at the ladder south of where you are. It will fall down allowing you to escape the room. After, leaving, go to where I said to NOT climb. Use your new slingshot to kill the Skullwalltulas. Now it is safe to climb.