NOTE: This Walkthrough will cover, each and every Heart Piece, Item, Boss, and everything else.
Now that Link has the Titan's Mitt, there are a few things that Link can get to before heading on over to the 5th crystal. From just outside Gargoyles Domain head all the way to the right and then all the way down a screen. Head left and talk to the frog there. He will ask you to take him to his partner. He will then start to follow you. Head right and back up a screen. Take the first right here. Use your mirror to get to the Light World.
Walk into the house here to re-unite the partners. Exit the house and then re-enter. Ask them to temper your sword for 10 rupees. Exit the house, head left a screen, then back right a screen, and back into the house and the sword should be tempered for you. Grab it and then head back outside. Head through the teleporter that was left from the mirror. In that same area in the Dark World, you will notice a bunch of stakes. Pound them all to reveal a passage.
Walk in and grab the quarter heart container that is here. Exit the cave. Head back left a screen. Head down a screen and then left a screen. Head all the way to the left and up the stairs. Talk to the man here to play the treasure digging game.
The rules are simple, you have 30 seconds to dig. Whatever you find, you keep. Somewhere here is a quarter heart container. Dig until you find it. If you dont get it exit right a screen and come back and play again until you get the quarter heart container. Afterwards head back to the building where you temepered your sword, but this time in the Dark World.
You will see a treasure chest here but you cannot open it. Go up and try to talk with it and it will tell you that you cant open it, but it will follow you. Do not run or the chest will be left behind. Take it with you and head left a screen. To make things easier, use your mirror here to get to the Light World. Head down a screen, right a screen, down a screen, and right another screen. Lift the rock at the bottom-right and head down. Head left at the first opening.
Head up and talk to the man by the sign and he will open the chest for you if you promise not to tell people that he use to be a theif. Afterwards, head right three screens and jump into the Lake. Swim up and right to the big island at the center of the Lake.
Lift the black rock here to reveal a portal. Head through it and you will find yourself just outside the Ice Palace head up into the dungeon.
Bring out your Fire Rod and head up and kill the freezor using the Fire Rod and head left through the door that opens.
Kill the three buris here and grab the key that is left and head down the stairs at the top. Press the switch at the bottom-left of the room. Kill the two enemies here and head right a screen.
Push the block to the right and head down. Use bombos to kill all the enemies real quick. After the enemies are all defeated open the chest for the compass and then head back up a screen. Push the block up and head right a screen. You can use bombos here again to kill the enemies. You can get a fairy from the anti-fairy usuing magic powder if you would like to. Lift the pot at the bottom, press the switch and head back left. Push the block to the left and head up.
Kill all the enemies in this room first to make things easier. Place a bomb next to the orb and quickly move to the top part of the screen. Place a bomb on the cracked hole and fall down. There are two Stalfos Knights here. One at the top-right and one at the bottom-left. Walk in those areas and they will appear. Hit them once and place a bomb on them kill them. Head down a screen.
Beware of the spikes, the moving platforms, and the enemies in this room. The second Buri from the right holds a small key, so kill him to get it. Head left and down through the locked door. Make sure the orb is on red. There is a switch under the pot at the bottom-left. Press it and then make your away around and head right a screen. Head down the stairs here. Use bombos to kill the enemies quickly and then head up a screen. Move forward a little bit here and a spike will come down at you. As it is reseting head left a screen.
Just head down the stairs here. Kill the two freezors here and a treasure will appear. Open it to get some bombs.
Place a bomb where it is shown in the picture. For now just fall down the hole that is on the right side of the screen and then head right. Head right a screen here as well.
Lift the first pot just above you to get a small key and then lift the pot at the top-right of the four center pots to reveal a switch. Press it and then head down a screen. Make your away around and head left a screen. If you are having trouble getting around this room, using your dash could help you out.
Lift the pot and Press the switch at the bottom-left to reveal a chest. Open it to get another key. Head up the stairs. Lift the first pot here for some arrows. Dont lift the other one unless you would like to be a rabbit for a couple seconds. Beware of the freezor that come out from the top-right. Make your way around and go through the locked door. Head up through this room and exit to the right. Hookshot accross and exit to the bottom. Make your way around the spikes here and head up the stairs at the top-left.
Kill the buris here and hookshot accross the spikes to the right side and head up the stairs. A stalfos knight will fall down. Use the same method of striking and placing a bomb. Use your hammer to hit the moles. Lift the rock and grab the key here.
Smash the other set of moles. Kill the other stalfos knight that falls down here. Lift the pots and step on the switch to make a treasure chest appear. Pull the tongue of the statue to make the door open on the right side.
Head to the right side of the room and open the chest for the Dungeon Map. Exit to the right. Head up the stairs here.
Lift the pots here and then open the chest to get the Big Key. Head back down the stairs. Pull the tongue of the statue here to open the door. Head back left a screen and down the stairs.
Lift the pot here and press the switch to reveal a treasure chest. Hookshot accross and open it for another small key. Head left through the locked door. Dash accross and exit to the left.
Go down the stairs here. Place a bomb on the left side of the room again and this time fall down the hole on the left side of the room. Open the chest to get the Blue Mail. Push the blocks and exit to the right a screen. Head up through the locked door. Unlock the door at the top and head down the stairs. Head down a screen here. Head right through the locked door. Hit the orb once. Grab all the items from the jars if you would like.
Head back left, up, and up the stairs. Head down a screen and right a screen. Press the switch at the top-right. Head down a screen, left a screen, and up the stairs. Head around and up a screen. Head to the top and right a screen. Head down a screen. Go around and head up the stairs. Head left, and left once again. Head down the stairs and fall down the hole on the right. Head right a screen. Because you hit the orb you can now have access to the blocks. Push the block at the bottom-left down and then follow it by falling in.
After Killing the enemies lift the pot here and push the block onto the switch. There are some items on the right side if you would like. Lift the pots on the left side and then pull back the statue on the right. Lift the big block at the bottom-left and then fall down to enter the boss room.
The first stage of the boss is rather easy. Just use your fire rod and hit him a bunch of times until his ice sheild has melted away. Beware the falling ice balls that spread once they hit the ground.
This stage is pretty fun. He will spread into three seperate eyeball-ice looking things. You can use your fire rod or your sword to strike them. Four hits with the Fire Rod or 8 hits with the tempored sword will kill each one.
Afterwards grab the Heart Container that is left for Link.
Grab the Crystal and list to the Maiden talk about the Hylian people and more about the Triforce. You will then be transported to just outside the palace.