From Darunia Town, once you know the Reflect spell, you should head east through the forest and then go across the bridge. To reach the palace from the maze, go south, then east until the first north path. Use it to go north, then head east when the path splits. Keep going north, going past the bridge on the left, then head across the bridge to the north.
From that small bridge, go west until there is a north path. Use it to go north, then go west, then west again when the path splits, then north when the path splits, and then go east every time the path splits after that. You will reach the Maze Palace.
At the entrance hall, there is an orange Moa flying around. You can try to hit the statue to get a red magic jar. If it turns into a red Iron Knuckle, just run away and leave the palace, then come back and try again. When you're ready, head down the elevator.
Head east. There are going to be some Wizzrobes appearing and disappearing in this room. You can cast the Reflect spell to deflect their magic, but it is better to conserve your magic and just jump over their attacks for now.
In the next room you will see a 100 point P-Bag. There are a couple of helmeted blue Stalfos in here. Head down the elevator.
In the next room, go to the right and fight the helmeted red Stalfos. Then cast the Jump spell and go east onto the crumbling bridge. When you reach the end of the bridge, jump to the right to make it over the gap.
If you don't make it over, you will land on some crumbling bridges on the floor below. Just jump down into the pit below these crumbling bridges. When you land on the crumbling bridge over the lava, run to the right. You must get past some floating statue heads, then in the next room break some bricks and jump over the flames to kill a Doomknocker, then later a red Stalfos. Try knocking them into the lava. Then get the key at the end of the room, head west back across the lava, get past the Bot and Wizzrobes and unlock the door, then take the elevator up past the inaccessible area with the lava and Bubbles, and finally exit to the right to get back to the room where you tried to jump over the gap.
Anyway, assuming you got over that pit with the single crumbling bridge over it, some Tinsuits will gallop toward you, and there is a Doomknocker a little farther into the room. If there isn't a statue on a tall pillar near the gap that you jumped over, you are on the wrong floor and need to drop down and follow the instructions in the previous paragraph to get to where you need to be.
Anyway, past the Doomknocker, you will get to the next room, where you must break some bricks and jump over the flames to reach a Doomknocker in the middle platform. Try to make it fall into the lava. If there is a red Stalfos in this room, you are in the wrong room, so follow the instructions two paragraphs up to get to where you need to be. Once you get past the Doomknocker here, get the key from the right side of the room. The statue here might give you a red magic jar. If it spits out a red Iron Knuckle, try pushing it into the lava.
Go back the way that you came. You will discover that there is no way to get back up to the crumbling bridge unless you cast the Fairy spell. However, you are supposed to jump into the pit, so do that. Try to jump to the middle part of the pit. You will land on a crumbling bridge on the floor below. Carefully jump to the floor on the right. If you fall into the pit, follow the instructions a few paragraphs up to get back to this spot.
Some Tinsuits will attack. There is a bubble in this room. There is also a Doomknocker. In the next room you must fight a blue Stalfos. The statue above doesn't have a magic jar. Then there is a blue Iron Knuckle guarding a locked door. Once you get past, you can pick up the boots. These just let you walk on certain areas of water in the overworld.
Go back the way that you came and drop down into the gap. You will land on a crumbling bridge above some lava. If you have not been here before, head east and get past the floating statue heads, then in the next room break some bricks and jump over the flames to kill a Doomknocker, and then a red Stalfos. Try pushing them into the lava. Get the key at the end of the room, and then go west, back across the lava area, then kill the Bot and avoid or kill the Wizzrobes. Unlock the door and go straight across to the next room. There are more Bots and Wizzrobes beyond the locked door.
In the next room, there are floating statue heads that spit energy at you. Break the blocks in the back of the room to get a key. Then return to the elevator and go up to the top floor. Go left past the two blue Stalfos, and in the next room go left past the elevator while avoiding the Wizzrobes.
Unlock the door, then kill the red Iron Knuckle. Cast Jump and use the upward thrust to get the key from the upper room. Use it to unlock the door. Go past the elevator and fight some Tinsuits and a Doomknocker. In the next room, there is a Doomknocker on the top level, a 200 point P-Bag, and a key. Get the key, then return to the elevator and go down.
First, go to the right, avoiding Wizzrobes and killing Tinsuits. In the next room, avoid the floating statue heads. Break the bricks and jump over the flames, then get the key at the end of the room. The statue might give you a red magic jar. If it gives you a red Iron Knuckle, knock it into the lava. Then go back to the left.
Go past the elevator defeating Tinsuits and avoiding Wizzrobes, and unlock the door. In the next room, carefully go over the crumbling bridges, using downthrust or just jumping over the Myus to get past. Take the elevator down.
Unlock the door and fight the blue Stalfos. There is a 100 point P-Bag on one of the platforms. In the next room, you must fight two red Iron Knuckles.
After that, you will have to fight Carock.
You need to use the Reflect spell to get through this battle, so cast it right away. Then go to one side of the room and face toward the middle while crouching. Carock will shoot energy waves at you and your shield will make them bounce back if you cast Reflect. The waves will then hit Carock and injure him.
The difficult part is that Carock appears randomly in the room, sometimes right on top of you. You will need to watch your life meter and cast the Life spell if you are running too low on energy. You might want to cast Shield before the battle begins. This battle shouldn't be too hard otherwise, because all you do is crouch and wait for Carock to destroy itself with its own magic.
When that is done, it is time to make your way to the Ocean Palace. When you exit the Maze Palace, if you got the Boots, you can just walk along the water to get to the exit bridge.
Once you are on the other side of the bridge, you can walk south along the beach and walk right onto the ocean. Keep going south on the ocean and then west onto the beach. From there you can walk to Nabooru town, avoiding the cave that you had to go through before. Heal up in Nabooru. Then you are ready to make your way to the Ocean Palace.