Go east from the entrance to the palace and fall off the ledge. Go a little south then continue east to a cave. Go in.
Follow the path to a room with a guy in it. He doesn't have anything interesting to say. There are cracks in the south wall, so bomb it and go through for a chest containing a piece of heart. Go back out to the desert.
Nothing left to do here, so go to the southeast area and exit. Before you leave the zig-zagging area, go to the middle where there are two large white stones. Pick up the bottom one to reveal steps. Go down.
The ten pots here each hide a 5 rupee piece, giving you 50 rupees. The guy here tells you about Lake Hylia, where we will be going later.
You can actually go in and out of this room and the rupees will be there every time. If you need cash, just keep going into the room and getting the rupees. If you go into the room 20 times you can fill your wallet.
You'll need at least 500 rupees for the next part, so if you don't have enough, use the rupee room to get however many you need.
Now leave the room, and first let's go to the witch's hut. It's kind of a long trek. From the screen with the rupee room exit east. From there exit north, then east, then north to Link's house. Go east from here, then up the bridge and north. Continue north, then go up past the wooden bridge (don't cross the bridge) and exit north. Go east from here and you find the witch's hut.
Avoid the green monster (buzz blob) by the way, if you hit it with your sword you get electrocuted. You have to stun it with your boomerang before you can hit it with your sword.
Equip the magic mushroom (if you didn't get the magic mushroom, it's in the Lost Woods, see the Village Elder section) and use it on the witch, who will take it and tell you to come back later.
Exit the screen to the left, then come back and go into the witch's hut. Next to the potion salesman should be a bag, get it! It's the magic powder, and I find the best use for it is to sprinkle it on bubbles, which turns them into fairies! You'll also need it for an upgrade later. (By the way, it also turns buzz blobs into cukemen, who give advice [though will still electrocute you].)
Go back outside, and go east of the witch's hut. There's a large white stone here, pick it up and go north and exit to the next screen.
Dash into the top pile of rocks below to get rid of it, then go east and up, beyond the green monsters, to the next screen.
Jump down from the ledge here and avoid the crabs or kill them (they take two hearts away if they hit you) and exit north along the shallow water.
Now you're in Zora's Domain, and there are zoras everywhere. If a zora whirlpool appears in shallow water, the thing will jump out of the water and start walking slowly towards you! If you hit the walking zora, you stun it, and you can actually pick it up and throw it. Feel free to just throw it back in the water if you don't want to deal with it. Funnily, if you hit the zora as it's jumping out of the water, it will go flying through the air in the direction you hit it!
Anyway, continue north along the shallow water. When the path turns east, go east, then when you see the shallow water going downward, go down it. Continue as far down as the shallows go until they head east, follow the path until you reach a large waterfall. A huge zora appears, this is King Zora. He'll sell you the Flippers for 500 rupees. That's a lot of cash, but you need them, so buy them!
Once you have them, go all the way down and swim down the waterfall. Follow the shallows (don't drop down these waterfalls) and you reach some land. At the far end is a piece of heart. This should be the fourth, giving you another heart container! Now go back to the waterfalls and fall down one of them, then head west and finally south to exit Zora's Domain.
Before leaving this area, swim into the center of the waterfall to the left. Inside is the Mysterious Pond. Go up to it and it asks you to throw something in. Throw in your boomerang. A fairy will appear, asking if you threw the boomerang. Say yes and she'll give you the magical boomerang in return! Don't leave just yet, you want to throw your shield in there too. The upgraded shield you get will stop fireballs like the ones the zoras spit out (but not beamos beams). It will even block fireballs when you're in the water! Note also that if you have an empty bottle, you can throw it in and she fills it with green potion for free! Now you can leave.
Swim into the water to the southwest. There's a permanent whirlpool there, if you swim into it, it takes you to Lake Hylia, so swim into it!
When you get to the lake, swim north onto the little dock to get onto the island. In the cave in here is the Pond of Happiness. If you throw in a bunch of rupees, a fairy will eventually show up and will upgrade your bombs or arrows (your choice) allowing you to carry more. She shows up each time you throw in 100 rupees. The maximum amount of bombs you can carry is 50, and the maximum of arrows is 70. After you reach the limit, the fairy will just give your rupees back to you if you try to upgrade. It's worthwhile to upgrade your bombs and arrows, you'll want to be able to carry a lot (especially arrows). To upgrade to the maximum you'll need 1,400 rupees. Remember that you can get infinite rupees from the room near the desert.
Note also that the wall to the right of the pond is cracked. Bomb it if you want some fairies.
After you're done upgrading bombs and arrows to however many you want to carry for now, leave the cave and swim north, exiting the screen to the north while still in the water. Follow the path until you can swim under the bridge. Under there you find a guy asleep. Talk to him and he gives you a free bottle! Now swim back to Lake Hylia.
Once you get to the screen with the Pond of Happiness cave, exit southeast in the water. Get out of the water on the dock here and head north. Take the eastern path north and you reach a cave opening, a bombable wall, and a large stone. The stone has stairs under it, but all that's there are 20 rupees and a guy who says nothing important.
Rather than go through the cave opening, first bomb the wall and go in. This icy cave leads to a chest containing the Ice Rod! This magical weapon shoots an icy beam that will freeze enemies on contact. This is the treasure at Lake Hylia that Sahasrahla was referring to.
Go back outside. If you go into the open cave and bomb your way to the next room, you get to a fairy fountain with a statue in the middle. If you dash at the statue, the magical bee will come out. The magical bee is a special bee that, if you catch it and put it in a bottle, will attack and kill all enemies on the screen when you let it out. I don't think it's that helpful, but you can catch it if you want. Otherwise you can catch a fairy for your new bottle.
Go back outside. Get in the water and swim along the left fork and down to the next screen. Go down the waterfall and swim into the whirlpool here to get to a small pond near the Sanctuary. Get out of the pond, then go up behind the tree and near the rock wall. Head east to end up on a hill where there is a pile of rocks. Dash at the rocks to break them, then go down the stairs for a piece of heart.