After you fall into a tiny crack of ice at Lake Hylia, you finds yourself in a cave with a giant frozen Octorok.
Go down the stairs. The ice around here is slippery, and there are edges you can fall off, so be careful. Go north, push the blocks of ice out of the way (if you push them straight ahead they keep sliding along the ice until they hit something), and go through the north door. From there just exit east. Beat the monsters if you want and go downstairs. Push the lever to open the trapdoor above and let the sunlight in. Notice the block with the key frozen inside. You need to melt it, so go back upstairs and drop down the trapdoor. Push the ice block down, then right, and it'll be under the sun and melt. Grab the key, then go right and push the block out of the way, and head back to the room with the locked door. Unlock and go through.
Drop down into the hole. To the right, the big key is frozen in a block of ice. To get it to the sunlight, first push the bottom plain block left, down, and left. Push the top plain block left. Then go to the big key block and push it left, up, left, down, left, up, and finally right under the light. The block will melt, grab the key. Now push the lever to close the trapdoor above. Go up the stairs and make your way to the entrance room.
This dungeon is a bit strange in that you go through the big door now (it's at the south end of the entrance room). You'll soon discover that the element is frozen in ice, and the boss is frozen below. There's plenty more exploring to do before you're done with this dungeon.
Exit southwest, and continue south to get the map. Go back north to where there's water and a rolling spiky thing. Get in the water, and when the spiky thing comes near, dive with B to swim under it. Exit west. Go up the stairs, get in the water and exit east, then south, then get out of the water. Use the gust jar to get the mushroom and launch across. Step on the switch and the gate at the waterfall opens. Get in the water and drop down the waterfall to the next area.
Swim south and dive to avoid the spiky thing, then at the bottom, you can read the tablet for a clue, then step on the switch to open the gate. Exit east. Get inside the pot-shaped formation, swim to the bottom center area of it, and dive down to retrieve a small key (you may have to swim around to find it). Go back the way you came, past the spiky thing, and climb up the wall to the area above the waterfall. Push the block out of the way and walk north to the locked door, unlock it and go through.
Follow the path, step on the switch to lower the gate, then suck the lilypad to you with the gust jar. Hop on, and gust your way north. Just follow the straightforward path through the water and gust yourself down the waterfall. Keep following the path, getting off the lilypad and diving to avoid the spiky thing. Continue east and you reach a small island with a switch on it, step on it to lower the gates. Continue riding the lilypad, and at the fork, go east.
Get off the lilypad and beat the Madderpillar like you did back in Deepwood Shrine. The battle is harder and more annoying because it takes place on ice. When you beat it, exit north. Grab the compass from here, then return to the lilypad, exit west, then exit north. Up above, step on the switch to open the gate. Continue north on the lilypad. Beyond the frozen chest, up north, there is an unfrozen chest that contains 50 rupees. Now you need to tackle the ice block puzzle below.
You need to get a block onto the switch, and the way to do it is to push the rightmost block left, the topmost down and left, the bottom-left block up, and then push the upper-right block left and up, onto the switch. Back on the lilypad, continue along the path past where the gate was. Continue north and east and through the door into a dark room. Carefully make your way along the ledge and exit north to where there's light again. Go up the stairs, and continue up to the first floor.
You have to beat the three mandible monsters to continue. Remember that you can't hurt them head-on, so hit them from the side or behind or wait for them to throw out their mandibles and hit them when they're vulnerable. When they're gone, a blue warp tile appears and the door below opens. Use the warp tile and exit south if you need hearts, then back in the warp tile room, go through the door.
Follow the path to a large lever. Your strength alone isn't enough to budge it, so clone yourself on the tiles below and have the two Links push it together. It will move and half the floor below (where the element and boss are) will be hit by sunlight, melting a small ice block in the way. Drop down and go through the path that just opened. Follow the path and you reach a chest containing a blue Kinstone piece. Continue on. To reach the chest below, take the bottom-left path first to get the blue Kinstone piece. Go back and take the bottom-right path next. You encounter a slow-moving ring of traps with an opening. Go through the opening when it passes to get into the center. The path to the right leads to a couple of pots, one of which hides a green Kinstone piece. After you get that, go through the traps to the path to the left, and go through the door.
Take the path where it leads you until you reach a hole in the floor. Go down the stairs, push the lever, then go up the stairs. Walk across the trapdoor and push this lever to let in some sun, then go back down and push that lever to melt the ice block. The chest holds a small key. Go back up to where there's a locked door, and go through.
Keep going and a gate will close behind you. Down below, push the lever and sunlight will stream in, then blue blobs will fall from above. You might remember this happening before the giant green chuchu boss appeared in Deepwood Shrine. This is the same, except the giant blue chuchu is electrified. You have to wait for its electricity to go away, then use the gust jar to shrink its base until it falls. Hit it a bunch of times, and repeat the process until you beat it.
A chest appears containing the Flame Lantern! Finally! It can be used to brighten dark areas, light unlit torches, and melt ice blocks.
Head back the way you came and use the lantern to melt ice blocks in the way (you can melt your way to the pots, they may contain hearts if you need them), then go down the stairs here. The frozen chest contains 100 rupees. The next room is dark and you have to fight three more of the monsters with the blue mandibles. Just turn on the flame lantern and fight, it'll stay lit. You'll probably end up lighting the torches in the room as you move around fighting. Once the monsters are gone, go through the east door.
With your lantern still lit, take the very bottom path and light the torch at the end to make the block above disappear. Go back the way you came and go down the path where the block just disappeared. You'll see a torch above, but before going to it, head southwest to reach the chest containing a red Kinstone piece. Then go back to that torch and light it to make the block disappear. Of the two paths down, take the left one. You'll see to the left a wall you can bomb. Blow it up and go through, then beat all the monsters to get a small key. Go back to the maze.
Of the two paths leading up, take the right-hand one. The chest contains a red Kinstone piece. Continue and you'll find another torch to light to get rid of the block in the way. Take the path where the block was. Get to the second chest for yet another red Kinstone piece, and light the torch. Go through the locked door that you can now access.
Be careful in here, if you get hit by one of the fiery things, you'll automatically run in the direction you're facing for a while. Make your way to the west exit. Carefully make your way across the ice to the next room. You can turn off your lantern now. Go into the door and you enter a hidden path. Once you can't move any further, start moving westward to get out and to the next room.
To continue, create two Links, one above the other, and push the top block as far left as it will go. Get rid of your clone so you can make two again, one beside the other, and push the bottom block all the way down, over the glowing tiles. Using the other set of tiles, create two Links side-by-side and push the leftmost block down one space. Get rid of your clone once again to create two Links, one above the other, and push the topmost block to the right so you can go through the door.
Push the ice block left. Make your way into the room and push the second block down and left onto the switch. Now you need to carefully make two clones, but spaced so they can maneuver around the blocks and step on the two remaining switches. To do this, stand on the topmost tile and charge up your sword, then with it still charged walk around the block to the third tile down and make the clone. Carefully make your way around the blocks to the switches all the way to the left. You may have to keep trying. Once you do it, go through the door you opened.
Stand in the doorway for a second to make sure you don't get hit by the fiery things. You have to get into the room and push the top right block up to open the door. Go through.
Defeat the enemies and melt the ice to reveal glowing tiles. Make two Links one above the other and push the block below to the right (it's under the ice bridge). The way out is between the two torches. Go up the stairs to the next area.
In here you have to get all 9 torches lit to open the way. Unfortunately the floor is slippery and the torches will eventually go out. You have to be quick, and keep trying until you get it. Once you do, exit.
Swim and dive your way south avoiding the spiky things. Don't even bother with the blue-mandibled enemies, just exit at the bottom right. Step on the switch to reveal a red warp, then bomb the north wall where the tiles point to get to the next room.
Argh. There are not one, but TWO Madderpillars in here, it's dark, and there are webs everywhere. At least the floor isn't slippery. You can burn all the webs down with the lantern to make your life easier. Work on the Madderpillars one at a time if possible, and once they're gone the way will open, so go through. Continue on the path and watch out for sluggulas from above on the ice bridge.
Eventually you get back to the room with the element and boss in it. Use the tiles to clone and push the lever to the left to let in more sunlight. The element will thaw out, but so will the boss, who sucks up the element and goes to the room below. Heal up with the hearts in the pots around the room, then follow the boss.
With the Water Element in hand, grab the heart container and take the green warp. Step onto the big tile above you to get warped out of the dungeon.
To find the next dungeon, you have to find a ghost.