Getting across the broken bridge
You can get Epona and ride to Gerudo valley. Get her running at full speed, and jump across the bridge gap. However, it is much easier if you have the Longshot. Use the targets strung on rope over the bridge ends to pull yourself over. Once across, talk to the head carpenter outside the little white tent. He will tell you that the bridge was destroyed by the Gerudo. Inside the tent, you will find the Hyrule Field runner. He won't do much for you now, but once you finish later sections, he will present a rather difficult opportunity in the form of an (unbeatable) race to the Lost Woods.
Scattered outside the tent are several boulders. One of them is hiding a treasure chest with 50 rupees in it. Once you've blown up all the boulders and collected all the goodies, follow the trail and ride/walk into the Gerudo's Fortress.
- Note: You can't do this prior to Forest Temple. You're not going to cross the blinding desert without the Longshot and Eye of Truth. Come back later with those two items so you can survive the two tests to be able to reach the Spirit Temple. Owning a Hookshot / Longshot, plenty of arrows and the Biggoron Sword will be extremely handy to make short work of the Gerudo guards. Saving the 4 carpenters would then become an easier job to handle.
It is possible to complete Gerudo Fortress prior to the Forest Temple, though there is not much reason to do so, since it is far more difficult without the necessary equipment and gaining the Gerudo Card is unnecessary at this point.
Be careful as you approach this area. You will find several Gerudo women patrolling this area and standing guard. The Gerudo dressed in white do not move, but are also undefeatable. Do not approach them at this point. Later, they will be of use, but for now, avoid them. The Gerudo dressed in purple are patrolling around the area, and can be defeated. They can be shot with arrows, which will knock them out. You may also use the Longshot to freeze them temporarily. Although useful (and it doesn't waste an arrow), they won't stay frozen long. In this frozen state, you can use your sword to knock them out.
In the event that you are seen, you will be taken away to a cell. Fear not; there is an exit. If you look around the top of the room, you will find a window with a wooden shutter above it. The shutter is targetable by the Longshot. If you target the far edge of the shutter, you will drop back down to the ground level, where there are 4 Gerudos patrolling. Although this IS where you need to proceed, you risk being seen again. It is better to target the near edge of the shutter and drop on to the edge of the window. From this vantage point, you can freeze/shoot/avoid the patrolling Gerudos. Once you get an opportunity, drop down to the ground level (and roll to avoid taking damage). There is an entrance to the left; go in.
Once inside, you will find a rather large, empty room. There will also be a jail cell to the left, and you'll see a man inside. He'll beckon your attention. Speaking to him, you'll find that he was 1 of 4 carpenters that decided to come here for riches, fame, and glory. Unfortunately, the Gerudo women didn't take kindly to the men and imprisoned them.
After speaking to the imprisoned carpenter, you'll be attacked by a Gerudo woman with some serious sword skills. During this dungeon, you will be forced to fight four such women, each more powerful than the last. Don't get cornered! Allowing the woman to land a spinning jump attack will "defeat" you, and you will be placed back into your prison cell. The best strategy to use to defeat her would be to keep her constantly Z-targeted (L-targeted for GameCube and Classic controller), use your shield, and keep your distance. If you do this, you can use the Longshot to freeze her temporarily, and slash at her while she's frozen. In order to keep the Biggoron's Sword equipped, switch back to the Longshot just before using the shield and you will put away the sword.
If you find that the spinning jump attack defeats you despite blocking with the shield, an alternative method is to Z-target (L-target) the Gerudo fighter and continually strafe left or right in order to avoid any attacks. When the fighter attacks, run forward and thrust with the sword (ie forward and attack). You should manage one, maybe two, attacks before she regains her footing, then get out of the way and wait for another opportunity.
After you defeat her, she will drop a small key, which you can use to release the carpenter. He will thank you and leave. Thoroughly explore the Gerudo Fortress, and find the other carpenters. Note that one of them can only be access by jumping from one of the high roofs in the complex.
If you are attempting to complete the fortress prior to the Forest Temple, you will need to rely on the hookshot to escape your cell if you are caught. This is the only item useful enough to help you through the fortress at this stage in the game. Release the carpenters in linear order starting from the door just left from the cell where you are captured. After the third carpenter is released the last is the most difficult to reach.
Moving on from the room where you found the third carpenter, you will head up a ramp and outside to the platform with vines on one side. Head into the next room with two Gerudos patrolling below in a kitchen area with a large cauldron on your far right. Using the hookshot, you can manoeuvre yourself across the higher platforms on the left of the room by aiming at the wooden ceiling beams (aim for the 3rd then the 5th ahead of you). You will reach the farthest door undetected. Head through the door and drop down to your left (Link's right); there is the final door in an alcove.
Now this next part is tricky, and may require a few attempts to complete. Immediately get behind the crate and hold up your shield/crouch. A few seconds will pass and a Gerudo will come from your right down the hallway, then stop. Make sure you are pressed up against the crate; as soon as she stops climb onto the crate (this will not make her turn around) and Z-target (L-target) her. As you quickly strafe right off of the crate then backwards down the hallway she will begin to turn around, but don't worry. If you were quick enough you will be far enough away to automatically un-target her, and she will not be able to see you. Quickly go right and you should be at the final cage. Defeat the Gerudo Fighter to get the key and complete the mission.
Using this method is challenging and ultimately pointless, but it is an option if you want it to be more of a stealth-based mission.
The Gerudo's Membership Card
After you've freed all four of the carpenters, the Gerudo in charge of the fortress will pay you a visit. As a way of commending your skills getting past all the guards, she'll give you the Gerudo's Card, which makes you one of them. Now you can visit the fortress without being jailed every time. In addition, now that the carpenters are all freed, they will rebuild the bridge, making it much easier to get back into Gerudo's Fortress. You can now also challenge the Hyrule Field runner (in the tent) to a race.
After you get this, head over to the large gate near the entrance of the fortress and climb the ladder nearby to the top. The Gerudo at the top will open the gate to the Haunted Wasteland if you speak to her, but you'll have to pass two trials to cross the desert.