The Gerudo Fortress is located in the Gerudo Valley which is found can be accessed in the western region of Hyrule Field. There are two options for getting across the valley – you can either use 
Longshot to aim for the wooden pieces of the broken bridge on the opposite side of the gorge.
Continue down the roadway towards the Gerudo Fortress and you will be captured by one of the female guards and thrown into prison. You now have to sneak your way through the Gerudo Fortress without being spotted by any of the guards. You can stun them by using your Longshot or shoot them with your 
Fairy Bow to knock them out in order to help you get past.
You can escape from the prison cell by aiming your Longshot up to the open window and hitting the wooden platform. Aim the Longshot up and you should land on the ledge of the window.
Run off of the ledge aiming towards the roof that you can see on the left side of the screen (shown in the screenshot). Go through the doorway on the east side of the platform.
Travel around the corner to the left and hide behind the crates by holding down the R Button to shield. Watch out for the patrolling Gerudo guard and then run down the hallway on the left side just past the crates.
There will be a stone wall blocking passage here but you can get past by using the Longshot on one of the wooden support beams in the roof. Follow the pathway up and back outside.
This platform is back out on the top of the prison cell that you were thrown into. There is a Purple Rupee in the crate up here (worth 50 Rupees) – roll into it to break open the crate.
Walk up to the railing and look to the left to see a treasure chest sitting on the roof. Use the Longshot to reach the treasure chest. Open it up to obtain another Piece of Heart (number 34 of 36).
Make sure that it is night time (play the Sun’s Song if you need to). Walk over to the south side of the roof that you are on to find a 
Gold Skulltula hanging from the wall.
Use the Longshot to kill it and to obtain the token (number 89 of 100). Head west (dropping down two rooftops) to find a doorway on the north side leading back into the Thieves’ Hideout and go through it.
Continue down the pathway to find one of the carpenters (that used to be in Kakariko Village) stuck in one of the prison cells. Speak to the carpenter and he will tell you that all of his friends have been locked up within the Gerudo Fortress. You will be ambushed as soon as he finished talking.
A Gerudo Thief will drop down from the roof and attack you. These duel wielding Gerudo Thieves can be difficult to defeat. After a certain amount of time they will use an attack on you that traps you and you will be thrown back into the prison cell.
The Gerudo Thief will drop a Small Key once you defeat her. Use the key to open up the prison cell and release the carpenter by speaking to him (Ichiro the carpenter).
Leave the cell and head left going up and out the other hallway. This will lead you back outside – quickly walk northward and go through the doorway on the north side of the building.
Move forward to find another carpenter in a cell. Another Gerudo Thief will drop down. Defeat her, obtain the Small Key and open up the prison cell to let Jiro the carpenter out of the prison cell.
Exit this area from the same way you came going back outside. Take the doorway to the left (on the east wall) and reenter the Thieves Hideout. Move forward down the hallway and take a right.
Go forward past the crate and take another right into a hallway which leads up and outside. There is a Gerudo Guard around the corner, so be careful as you come around, hop onto the ledge and then go into the door on the left.
Continue onward to find another cell (next to an empty one) with another one of the locked up carpenters. Speak to him to initiate the battle against the Gerudo Thief.
Defeat her to obtain another Small Key and then open up the cell to free Sabooro the carpenter. Exit the room out the top – the opposite doorway that you came in from. There will be a door immediately to the left – go through it.
The next room has a large eating area with a number of guards rotating around through it. Use the Longshot to target the wooden joists on the far side of the room.
Take the ramp up and out to return outside of the Thieves Hideout. Immediately to your left is another door on the lower level roof. Go through the doorway to find a hallway but be careful as there is a Gerudo Guard wandering back and forth.
Use your Longshot and wait for the guard to patrol past. Hit the guard with the Longshot to stun her and then run past her down the hallway. Follow the hallway down to find the fourth and final carpenter.
Defeat the next Gerudo Thief just like the previous three and then release Shiro the carpenter. Rescuing the last carpenter will cause a Gerudo Thief to come down and comment on your sneaking and thievery skills.
She will offer to allow Link to join their ranks and will provide him with the Gerudo’s Membership Card. This will allow her to access different areas of the Gerudo Fortress unimpeded.
There is now a mini-dungeon that you can complete called the Gerudo Training grounds. Make sure that it is day time and then speak to the Gerudo Thief wearing white and standing out front of one of the doors (shown in the screenshot below). The Gerudo Training Ground instructions can be found below:
Following that, call Epona and head down the pathway leading southward away from the Thieves Hideout (leading to the large open area on the east side of the mini-map).
Heart Piece (Gerudo Fortress)
Completing the Horseback Archery mini game to obtain the second last Piece of Heart by obtaining 1000 points.
Biggest Quiver (Gerudo Fortress)
Completing the Horseback Archery mini game to obtain the Biggest Quiver (holds 50) by obtaining 1500 points.
Return to the Horseback Archery area at night time and travel down to the furthest target to find a Gold Skulltula attached. Defeat it with the Longshot and obtain the next token (number 90 of 100).
Travel to the north in the Gerudo’s Fortress to find a large stone gate blocking the pathway into the Haunted Wasteland. Speak to the Gerudo Guard at the top of the gate and she will open the gate for you, but not after giving you a quick explanation of what to expect (the two trials). Continue through the gate an onward into the Haunted Wasteland.
