Gerudo Valley
Go back to the Hyrule Field, call Epona, then gallop to the Gerudo Valley, west of the field. You can cross the bridge with Epona or by using the Longshot. Go straight ahead and you will get caught by guards.
Gerudo Fortress
In the jail, look at the ceiling and fire the Longshot at the plank to drag yourself to the opening. Then, jump to the bottom and take the passage on the left.
Thief Hideout
Talk to the carpenter in the cell, then fight the Gerudo thief with the Biggoron Sword (or Master Sword). Be careful, don't let her hit you with a spinning attack or you will have to start back from the jail. Pick up the Small Key, free the prisoner, talk to him and go on.
Once out, turn left (Link's left), then in the corridor, watch out for the Gerudo guard in the back. Don't get too close and shoot an arrow at her to stun her. Turn left carefully and get rid of the next two guards the same way. You can play the Song of Storms near the wood stove to make a fairy appear, then climb the slope in the back. Once out, turn right (Link's right), get down one level and go straight ahead. Prepare yourself right away to shoot an arrow at the guard, then turn right, then left and talk to the second carpenter. Fight the second Gerudo thief, take the Small Key and free the man.
Backtrack and once out, get down one level, turn left, climb the vines and follow the passage ahead. Here is the third prisoner, use the same method to free him.
Get out from where you came in, turn left (Link's left) and get down one level. Get close to the edge and stun the guard below. Then, jump to the bottom and take the path behind you. Follow this corridor and free the last worker. A Gerudo thief will then appear and give you the Gerudo Membership Card, a pass that enables you to walk freely within the fortress.
You can now play at the Horseback Archery Range east of the fortress, but don't enter the Gerudo Training Grounds yet (bottom right corner of the map). Now head to the huge gate north-west on the map and climb the ladder nearby. Talk to the Gerudo so she lets you through and tells you about the next two trials to come: the River of Sand and the Phantom Guide.