To power up the Master Sword, Link first needs a treasure from the mysterous Fire Mountain island.

Freeze the Fire
If you don't have Ice Arrows, warp to the Mother and Child Isles to get them. You have to warp, not sail, to get them. Then, if you haven't already, warp to Dragon Roost Island and sail one square south to Fire Mountain. Get it marked on your chart, then get somewhat close to the island and shoot an Ice Arrow at the flames spewing out of the top to stop the fire.
This starts a 5 minute timer, so use your sail for a moment to crash into the island, then climb up onto the island and make your way up the ramps. If you came here by going south from Dragon Roost Island, there should be a ledge straight ahead that you can climb onto from the water. If any Kargaroks attack, you can optionally use the Grappling Hook to get a Golden Feather from it, then defeat it with your Boomerang or sword. (There is a Piece of Heart that you can get if you have 20 Golden Feathers.) Continue going upward on the island, and when you reach a fork in the path, go right. Sidle across the ledge, keep climbing, then fall into the hole at the top.
Get the Power Bracelets
Inside, the 5 minute countdown will continue. Use the Boomerang to defeat the Keese, and try to defeat the ones farther away with the Boomerang. Jump across the platforms on the lava, defeating Keese along the way if they are still there. The lava platforms disappear after you stand on them for a little while, so be quick, but jump carefully. At the other side, defeat the Magtails with a parry attack, or just make them roll up and defeat them with your sword. A chest will appear. Open it to receive the Power Bracelets. This stops the countdown timer.
Turn around, pick up the giant stone head, and throw it somewhere. Go through the new door and defeat or ignore the Keese, then enter the sparkly light to go up.
Get a Piece of Heart on Outset Island
Now that you have the Power Bracelets, you have access to another Piece of Heart. First, warp to Outset Island. Go up to the pig pen. If you put the three wandering pigs into the pen earlier in the game, there will be a huge black pig in the pen now. If you didn't put the pigs into the pen, read The Game Begins to find out how.
Pick up the giant pig and take it out of the pen. Be careful not to drop it or throw it into water, because it is very difficult to get it out. Carry it across the bridge to the area near the grass-cutting guy's field. Put the pig down on the place with two black spots on the ground. Scatter some all-purpose bait on the black spot on the right, and the pig will dig up a Piece of Heart.
Learn a New Song on Headstone Island
From Outset Island, sail east to Headstone Island. Go to the little beach and use a hyoi pear. There is a Piece of Heart on top of the island as well as rupees, so fly around collecting them and return to Link to obtain the items.
Then go up the beach and pick up and throw the big stone head, then go into the cave opening. Inside, stand in front of the slab and use the Wind Waker. Press right on the D-stick to switch to 6/4 time, and play the song. You will learn the Earth God's Lyric and a clue to finding the Earth Sage.