NOTE: For this next part you'll want to have a full quiver of arrows, so make sure to restock if you're low. One of the shops in Kakariko sells them.
Get to Gerudo Valley.
Remember, you want to have as many arrows as possible before doing this part. You'll want to get across to the other side of the bridge, and you can use Epona or the longshot. Get across whichever way you like.
Turn it to night and longshot two skulltulas in this area: one behind the tent, and one on the rock arch.
If you talk to the chief builder guy, he says all his workers were kidnapped by the Gerudo and asks if you can go and save them. Of course you can!
You want it to still be night time. Exit to the Gerudo Fortress.
If any of the Gerudo guards sees you, you get thrown in jail. That isn't a problem, because you can just use your longshot on the piece of wood over the window in the jail cell to get out.
If you want to avoid jail, go past the stairs and carefully walk up the slope, watching for a Gerudo guard to the right. Don't let her see you! Stand in a position so you can shoot her with an arrow without her seeing you. (The arrow will only stun her, not kill her; these girls are tough!) Then go through the nearby door into the fortress (the door furthest to the left).
(If you got thrown in jail, drop down from the window and go through the first door on the left.)
Inside you find a jail cell with one of the unfortunate carpenters. Talk to him and all of a sudden a Gerudo with two huge scimitars drops from the ceiling behind you. Turn around quick and lock on to her.
You may want to switch back to the Master Sword if you've been using Biggoron's sword, because you'll want to be able to use your shield to block. If you get hit too many times by this girl, you get tossed back in jail. Your chance to attack is after she does a jumping attack towards you. Start moving to the side when you see her crouch (which means she's about to do the jump) so she doesn't hit you, then strike.
After you defeat her she jumps into the ceiling and somehow disappears, leaving behind a small key. Use that key to open the cell and talk to the carpenter to free him.
From here, exit left from the cell and to a door to the outside. Go through.
Quickly go through the door to the left. Make a right and watch for a Gerudo guard to stop by the crate at the far end of the hall. Use an arrow on her or wait for her to go back, then take the exit to the right. Outside, carefully go straight ahead. There will be a Gerudo guard on the ledge to the left; you'll want to shoot her from around the corner. Then hop up onto the ledge and go through the door here. Straight ahead is another cell; talk to the carpenter to make another Gerudo girl attack from behind. Defeat her as before and get the key, use it on the cell and talk to the carpenter to free him.
Exit through the passage to the right of the cells.
Climb down the vines ahead, and go through the door straight ahead across from the vines. Simply talk to the carpenter and fight the guard to free him, then exit the way you came in.
Go back up the vines and take the left door. There are guards straight ahead, stay where you are and you'll be able to shoot one with an arrow, then walk a little bit further in to shoot the other. Go up the far ramp to the outside.
Get the gold skulltula on the wall, just stand on the corner and you can get it with your longshot. It won't be there if it's daytime. From here, jump down to the right and go through the door. STAND STILL when you enter, and shoot the guard who walks by. Go right and free this carpenter like all the others, and that's it, they're all free! The Gerudo girl will hang around to tell you that you've gained membership in the Gerudo clan for recklessly storming the fortress and getting past all the guards. Once you have your membership card, you can stroll through the fortress and the guards will leave you alone.
Before continuing, take Epona to the archery range behind the fortress. If it's night there will be a gold skulltula on the far tall target. If it's daytime you can play the archery game; the prize for the first win is a piece of heart, and the prize for the second win is the biggest quiver.
Then go back to the fortress. There is a
Now you can get the Ice Arrows. There's a sort of mini-dungeon here called the Gerudo Training Ground, and if you get through it you win the arrows as the prize. The door to the training ground is in the fortress, a Gerudo in white clothes is standing guard. Here's how to get through it.
There are no gold skulltulas in this mini-dungeon, and there's no boss. There's not even a map.
From the entrance, exit left. In this room you have to kill two Stalfos in a limited amount of time. Not too hard, though you'll sink in the sand unless you wear the Hover Boots. Try to get the Stalfos to attack and leave themselves vulnerable. For killing them you get your first key.
Go to the next room where you have to collect 5 silver rupees in a limited time. There's a wallmaster in here so watch out. There are rolling boulders and walls of flame to avoid, so watch your step. Get the first two rupees going into the left corridor. At the far end of the hall the way is blocked by a wall of fire so go back to the place you entered this hallway. In the middle of the center hallway is another silver rupee, you have to use the longshot to reach it. From there, go into the right hallway. Take a right from where you enter and go to the end, the fourth rupee is at the end to the right. Finally, go back to near where you first entered this room and get the fifth rupee here. The direct path to the door is blocked by fire, use the longshot to get past it. Continue on to the next room.
Kill the three wolfos in here. Ignore the door on the wall, it's fake. In here there's a giant block that you can't push equipped as you are. You need to go to the next dungeon to get an item if you want to push it, but you don't have to. There's a key back there but if you follow the walkthrough you'll get enough keys to win the ice arrows.
To continue, use the lens of truth and look at the right wall, where there's a hidden passage with a longshot target. Use it, step on the switch if you want to open the original door you came through. Otherwise go through the exit behind the fake wall.
In this room, turn left and jump off the edge of the ledge onto the stone circle below, which will start spinning. You have to shoot out all the eyes on the statue in the center. Once you do, a chest will appear containing another small key. Use the longshot to get it, then exit through the one door on this level.
In this room, kill all the monsters to unbar the door and reveal a chest containing arrows. You have to use the megaton hammer on the totems around the room to find a switch. It's under the totem on the left side of the far wall from where you entered. Once you find it, step on the switch to reveal a chest containing a small key. Continue through the next door.
To get around this room and get the rupees be very careful and use the hover boots. You may fall in your attempts, but just keep trying. Be sure to collect the key sitting on the ledge to one side of the room as you go along. Play the Song of Time near the center of the room to make blocks appear leading up to it. There is one silver rupee surrounded by fire. Leave it for last, the switch is below the ledge with the key. You have to carefully cross the room with the hover boots to get the last rupee. Once you get all the silver rupees, the bars will go up revealing a new room.
In here, play the Song of Time to clear away the blocks in the center. Get in the very middle of the water and put on the iron boots to sink to the center. If you aimed right you land on a silver rupee. Carefully get out from the path of the razor trap and start killing the shell blades around. Collect the rest of the silver rupees, floating when necessary. Once that's done the chest with the key appears, so get it.
Exit the lava room at the far end, the other side from where you first entered. In this room you have to bomb the beamos and kill a couple Dinalfos under a time limit to get the silver key. Now you can exit this room into the entrance hallway (use the exit that has a hallway leading to it, not the door with the symbol above it).
From here, exit right and you're in a room with caged areas and a bunch of locked doors. This is why we collected so many keys. If you get all the keys in the training ground (including the one behind the giant block, which you can only move after visiting the next dungeon) you will be able to unlock every door here, but there are two doors to the right of the entrance that don't go anywhere useful and it's a waste of keys to unlock them unless you have all the keys.
Start by unlocking the door to the left. There's actually yet another key available within this first room, look through the ceiling with the lens of truth to find an area to which you can climb by grabbing onto the cage and going up. Once you've got that key, continue unlocking the doors on this path. If you unlocked the two doors you see to the right of where you entered the cage room, you wasted keys.
Once you've unlocked all the doors and gotten to the center, you get the prize: the ice arrows. These will hurt your enemies and freeze them temporarily.
Now you can leave the training ground.
Before you leave, get the piece of heart in the chest on the roof of the fortress. You can go into the fortress and make your way to the roof, playing Scarecrow's Song up there to get across to the chest, or you can longshot onto the windowsill of the jail cell, jump down onto the fortress, and go inside to get to the area above the jail cell.
Now let's go out to the Haunted Wasteland. Go to the big gate down from the hill where the fortress sits. Climb up the ladder to the Gerudo above and talk to her and she opens the gate. Epona can't come with you through the gate so just walk through.