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 (if your controller supports it and vibration is enabled) and you'll hear a noise, and the A button on the screen will light up. 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 or a searchlight shines on 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. Make sure to stop moving if a searchlight is about to shine on you. 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.
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.
This searchlight (the southwest searchlight) was the only one that was 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. If you didn't disable the western searchlight, you can optionally go through the arches in the left wall, go up the ramp, up the ladder, and defeat the Bokoblin, then return to the hallway. 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.
You can optionally disable the nearest searchlight if you go through the archway on the left and go up the ramp, then go up the ladder, and fight the Bokoblin like before. When you're done, go back down the ladder, go back down the ramp, and get back into the hallway.
Go through the door at the northeast 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 (hold R on GameCube or ZR on Switch 2 to grab it, then move the control stick to push it), 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.
Press A to climb onto the wooden crate, then 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 control 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. Afterward, you will be on Windfall Island.