Link joins the pirates to follow the giant bird to the Forsaken Fortress.
Enter the Fortress
Walk toward the stairs and your controller will vibrate and you'll hear a noise. Press A and Tetra will talk to you through the pendant she slipped into your pocket. If the A button is shown on the screen again, press it to hear what Tetra has to say.
If You Get Caught
Since you do not have a sword at the moment, if a guard sees you, you will be thrown into a jail cell. If this happens, climb onto the table, then jump onto the bookshelf, then move the vase, then crouch to crawl into the hole in the wall. After you get out of the crawlspace, follow the path to find a chest that contains the map. Then skip to the Get a Piece of Heart section below.
How to Avoid Getting Caught
There are barrels all around the fortress that are big enough for Link to hide and walk around in. Just press A in front of a barrel to pick it up and hide under it. Then you can walk around while hiding in the barrel, and stop moving when you need to avoid being seen.
Disable the Western Searchlight
From the area where you first arrived, hide under a barrel, and go up to the area where the searchlights are shining. There are rupees in this area if you want to try to get them without being seen, or you can wait until you have disabled the searchlights that are shining on this area. If the searchlights are still shining here, be sure to stop moving when one of the searchlights passes.
When you are ready to move on, ignore the big wooden door nearby, and instead look for stairs leading up from this area. Keep hiding under the barrel and make your way up those stairs, stopping if the searchlight shines on you. At the top of the stairs, you will reach some arches in the wall that lead to a hallway.
From here, you can optionally go up the stone ramp nearby to reach a ladder that leads to the western searchlight. This searchlight just shines on the middle area with the rupees, so you don't have to disable it if you don't feel like it.
If you do want to disable it, you will need a weapon to fight the bokoblin there. You can either do what Tetra says and use your shield to make the monster drop its weapon, or you can look for the vase nearby that has sticks in it. Pick up the vase and throw it, then pick up a stick. Once you have a stick, swing it with the sword button to defeat the bokoblin. If a dark orb appears after you defeat the bokoblin, hit it to get rewards.
Get the Map
Go back down the stone ramp, to the arches that lead to a hallway. Go into the hallway, then go through the door on the west side.
Use the rope to swing across to the treasure chest, which contains the map.
Get a Piece of Heart
After you open the chest that contains the map, you can get a piece of heart. From the chest, drop to the lower level. Avoid letting the rats hit you, because you will lose some money if they do. Go past the barrels in the corner to find the switch that opens the jail cell here. Go into the jail cell and open the chest to get a Piece of Heart.
Disable the Southwest Searchlight
To proceed from here, it is quicker to get caught and thrown in jail, so go into the east hallway and let the moblins see you. In the jail cell, climb onto the table, then jump onto the bookshelf, then move the vase, then crouch to crawl into the hole in the wall. After you get out of the crawlspace, follow the path, and you will be back at the chest that contained the map.
Use the rope to swing to the other side, then turn left and go through the door in the northwest wall. Go through the arch to your left, and go up the ladder there. You will need a weapon to fight the bokoblin. You can either do what Tetra said and use your shield to make the monster drop its weapon, or you can look for the vase nearby that has sticks in it. Pick it up and throw it, then pick up a stick. Once you have a stick, swing it with the sword button to defeat the bokoblin. If a dark orb appears after you defeat the bokoblin, hit it to get rewards.
The southwest searchlight is the only one that is required to be disabled to proceed, so you can ignore the rest if you wish.
Get the Compass
Go back down the ladder from the southwest searchlight area, then go through the arch to return to the hallway. Go through the east door. Go to the left, and go through the door in the east wall. Go east through this hallway, then go through the door in the east wall. Then go straight ahead and open the chest behind the two barrels to get the compass.
Reach the Tower
After you get the compass from second floor of the southeast room, jump onto the rope to swing across. Go through the door, and go through the door at the end of the hallway to reach the second floor of the easternmost room. Jump onto the rope to swing across, and go through the door that leads northwest.
Outside, if you turn left before you reach the door in the northwest wall, you will see a wooden crate. You can push this off of the edge, then climb down the ladder and push the crate below the base of the ladder, to create a shortcut in case you get caught. If you do get caught at this point, swing across from the chest that had the map in it, then go through the east door and make your way down the stairs to reach the large central area. From there, you can reach the wooden crate that you pushed down below.
Climb onto the wooden crate, climb up the ladder, and go through the northwest door.
Pick up the nearby barrel, and sneak past the moblin to reach the stairs to the north. Go up the stairs, drop the barrel, and go through the door.
Outside, make your way up the stairs, and pick up a barrel when you find one. Sneak past the moblin up ahead, and go up the ramp to the left.
When you reach the narrow ledges, walk up to the wall and hold the A button when it says "sidle", then hold A and use the D-stick to sidle across. After you have made it past the two ledges, go up the stairs until you see your sword. Pick it up when you can, and defeat the bokoblin. Then go through the door and watch the cutscene.