Before you can reach the Water Temple, you need to go through the Ice Cavern in Zora's Fountain, where Lord Jabu-Jabu used to be.
How to Find the Ice Cavern
You will need the Hookshot before you can get through the Ice Cavern, so read the Temple of Time page if you don't have the Hookshot yet.
In Zora's Fountain (behind King Zora's throne in Zora's Domain), there is a large block of ice where Jabu-Jabu used to be. Climb onto it. From the high end you can jump onto a round block of ice. Jump toward the right, where there is a piece of heart waiting for you on an ice block. Then jump from block to block in the other direction, into the cave entrance across the fountain.
Ice Cavern
Follow the path through the cavern, being careful to avoid the falling icicles, until you reach a large room with a small spinning razor trap. Carefully kill the Freezards, then go through the door that opens.
Follow the path you reach a room with a large spinning blade in the center. You need to collect all five silver rupees to open the way. Avoid the blade and get the silver rupee near the center, then quickly follow behind the blade and collect the next two rupees the same way. Then cut the icicles down near where you entered the room. The fourth rupee is there. While in this area, you can use the hookshot to get the gold skulltula nearby. Finally, climb onto the ledge where the bars are, and jump from it to get the last rupee. The door will open, so climb up and go through.
Follow the path to the next room, killing the Freezard on the way, or just ignoring it. In the large room, kill the ice keese with the hookshot. Try not to let it hit you, or you will be frozen. Climb up onto the ledge, wait for the Freezard to stop blowing cold air, then kill it. Then jump to the platform with the blue flame. Empty one of your bottles and use it to catch some blue flame. Then wait for the next Freezard to stop blowing cold air, then kill it. Then go to the chest frozen in red ice. Melt it with the blue fire and open it to get the Map, then jump back to the blue fire platform and catch more blue flame.
Go back to the room with the large spinning blade. There are red ice walls to the left and right. Walk up to the one to the left (with two jars next to it) and melt it. Go through and follow the path to the next room.
There are a lot of falling icicles in here, so don't stand still too long. First, run straight across, cut down the icicles, kill the keese with the hookshot, and catch some blue fire. Now go to either side of the room where there are icicles to cut down. Kill any keese in the area, then melt the red ice. On one side of the room, you get a piece of heart and a gold skulltula, and on the other side, there is a chest containing the compass. Before leaving this room, catch some more blue fire, then leave.
In the room with the large spinning blade, go straight across and melt the red ice, then follow the path to the next room. Get rid of all the ice keese in here, then get the gold skulltula on the wall to the left of the entrance. Be careful not to fall off the edge.
Next, push the ice block in the direction away from where you entered the room. When it hits the ice, push it left. When it hits the next bit of ice, push it right, then left, then right, and it will hit the wall just below a blue fire spout, so climb up and catch some blue fire. Now push the ice block off the edge so that a new ice block rises up from the ground where you found the first one.
Push this one away from the entrance like before, but this time when it hits the ice, push it right. It will end up below a ledge with a silver rupee encased in red ice. Melt the ice and collect the rupee. Jump back down and push the ice block off the edge to create a new ice block.
With your back facing the way you entered, push this one left so it hits the thin ice spire with a rupee on top. Climb up and collect the silver rupee, then carefully drop back down to avoid falling off of the edge. Push the ice block right, climb up and collect the silver rupee, and before going back down, jump to the ledge with the blue fire and catch some. Then push the ice right, climb up and collect the rupee. Push the ice right again and collect the rupee, then push the ice right one more time and it will stop just below the exit. Climb up and leave.
Kill the freezzards on the way. At the end of the path, melt the ice and go through the door. Walk farther into the room to fight a white wolfos. Kill it as you did the Wolfos in the Lost Woods. Open the chest to get the Iron Boots. Sheik appears, and teaches you the Serenade of Water. If you haven't rescued King Zora yet, don't warp to Lake Hylia yet. Instead, walk to the pool of water behind the chest. Equip the iron boots and jump in. At the bottom, open the door and follow the path out of the water. You'll be in the second room of the dungeon.
If you still need to rescue King Zora, you need to get more blue fire, so go left after leaving the crystal room. When you arrive in the room with the large spinning blade, go right catch some blue fire. Now you can exit the cave and go back to King Zora. When you thaw him out using the blue fire, he will give you the Zora Tunic in thanks. This tunic allows you to breathe underwater.