Many rooms have Wallmasters that fall from the ceiling; these giant hands will grab you and pull you back to the entrance of the dungeon. Watch for shadows on the ground and listen for the "falling" sound, and get out of the way to avoid getting grabbed. Even if you kill a Wallmaster, more will fall.
Anyway, onto the dungeon. Avoiding the falling Wallmaster and the mummy-like Gibdos, head south to where you see a chest. Wait for the Wallmaster to fall, then pick up the three skulls in the way (don't want to get stuck in the narrow path and risk getting caught by the Wallmaster) to access a small key. Use it in the northeast locked door.
To get rid of the pink hardhat beetle quickly, just hit it into the hole to its left. Walk onto the stars above to move the holes to new locations so you can grab the chest for the map. Then exit west, then south out of the dungeon. (You'll be going in and out of the dungeon several times as you go along.)
Just like in the Lost Woods in the Light World, there is a hole in the center of the bushes above you, so cut the bushes and fall below, back into the dungeon.
Get out of this square of skulls, avoiding the circling fireball, and kill the hiploop with the skull you are carrying, or kill it with your hammer. Step on the stars below to rearrange the holes, then bomb the west wall and go through to the next room.
Pull the lever in the wall and suddenly the cracked south wall will explode apart (somehow there is no flying debris to hurt you). Go south, avoiding the moldorms, and you find the big chest, but you don't have the big key yet so you'll have to leave it be for now. Instead, use your hookshot to get across either of the two holes, and exit south to the outside once again.
To the northwest are ribcage tunnels; pass through them to another Skull Woods Palace entrance. Go back inside.
A Wallmaster is lurking in this room, so be careful not to let it grab you. You probably should kill the two Bari (use the hookshot) and the two Gibdos to make things easier. Lift the pot in the narrow path to the north door to find a switch. It needs something heavy on it to keep it pressed down. The right-hand statue can be moved. Push the statue onto the brown block to get it in line to PULL onto the switch (not push; you want to be behind the statue so you can go through the door!). Pull the statue carefully, avoiding the blasted Wallmaster, and exit through the north door.
You may be tempted to stay in the doorframe to avoid getting hurt, but the Wallmaster can get you there, so quickly walk into the room to avoid that grisly fate. Do NOT lift the skull in here; it hides a yellow swirling thing that will turn you back into a defenseless bunny! Kill the enemies here and carefully get past the spike trap to access the chest containing the Big Key! (If you're in need of magic, bomb the right wall for a skull hiding a large magic jar.) Exit south twice to get back outside (again! blah!).
You will want to return to those nine bushes with the hole in the center and drop in. Step on the stars (only the top ones) and exit west to the room where you broke open the big wall leading to the big chest. Go down to the big chest and open it to find the Fire Rod! Now walk to one of the holes and hookshot across, and go back outside yet again.
Go back through the ribcages to get to the other dungeon entrance. From here, exit west, then straight across to the next room, then pick up the upper-left skull to find a small key. Go outside.
Go through the left-hand ribcage tunnel to find an ugly, skeletal monster statue of some kind. It's right where the Master Sword clearing is in the Light World... how vile. Anyway, the secret to this weird statue is to use the fire rod on the tip of the narrow thing sticking out. Once you do, the narrow thing will burn away, and the face's mouth will open. Go inside to the next part of the dungeon.
Go down the stairs, then head as far right as you can go (there's a wall hidden under the walkway). Walk north until you can't go further, then go right, up, and left until you can't go further. Wait for the circling fireball to go to your left, then go up, right, stand in the upper-right corner to avoid the fireball, then go all the way left again, then quickly up to avoid the fireball. From here, go left, up, and around to the door. Go through.
Get up on the narrow walkway and go straight down, killing the Gibdo, then drop off the ledge and go through the west door to find a chest containing a small key. When you go back to the last room, remain in the doorframe to avoid the swirling yellow thing, and kill the Gibdos from the doorframe. Make your way north past the spike traps to the hidden wall room. Navigate the walls, going south, and go up the stairs at the south end of the room so you can walk up the walkway, killing moldorms, and go through the north locked door.
This is a confusing room with a lot of star symbols and moving holes. Even worse, a Wallmaster will be falling from above, and you have little room to avoid it. Step forward onto the stars at the entrance. Pick up a skull and walk to the stars in the center of the room. Now go to the bottom-left corner of the room and step on the star. Pick up the skull and walk north to some more skulls. Get them out of your way and walk east, then step on the top-right stars. Finally, step on the single top-right star, pick up the skull, and exit the room.
You have to act fast in this room to quickly light all the torches with the Fire Rod to open the door. First, go around and kill all the Gibdos, and lift the two skulls in front of one of the torches. Unfortunately there is also a Wallmaster here which may get in the way of your shooting flame. Go to the south part of the room and wait for the Wallmaster to fall, and kill it if you wish. Then light the bottom torch, run up and light the two middle torches, and run up and light the final torch at the top, then quickly run through the door before any of the torches go out.
Because of the Wallmaster in here, you can't stay in the safety of the door frame, so walk out into the room, avoiding the monsters and the swirling yellow thing. Kill what enemies you can, then cut the vines in the center of the north wall to reveal a hidden doorway. Go through it.
If you can, just go through the locked door, as you should have a key. If not, kill the Gibdo to get one. You'll have to use a skull on the hiploop. At any rate, go through the locked east door.
Be super-careful in the next room; you'll have to wait for the spike trap to pass after lifting a skull, but a Wallmaster will try to fall on you as you wait! Don't let yourself get dragged all the way back to the entrance now; you're almost done with the dungeon! Once you get past a spike trap, if you're ready for a boss fight, drop into the hole to meet...
-- Mothula --
This terrible flying creature is not so bad on its own, but to complicate things, the floor moves up, down, left, and right randomly, and there are spike traps all around the edge, some of which will randomly move across the room as you fight, all while Mothula shoots out circular beams! Bleah! Mothula shoots three beams, The beams shoot out at an angle left and right, as well as straight down the center. Avoiding the dangers, use the Fire Rod against the beast until you run out of magic, then use your green potion for a refill, and shoot with the Fire Rod some more. The spike traps will shake for a moment before they move, so if you can manage to notice that, you can try to avoid the oncoming trap. Do your best, and use fairies if you need to. My advice is to go slow, and don't try to attack every second. Spend some time avoiding the traps until you get a clear shot at Mothula. The Fire Rod takes so much magic that you don't want to waste magic by missing your target.
Once you have vanquished your flying foe, stand in the explosions to receive your heart container, then catch the crystal that falls to the center of the room.
The maiden inside tells you the prophecy of the Great Cataclysm (a big word meaning "destruction of everything", essentially). She says that if an evil hand touches the Triforce, it is foretold that a Hero will appear. The Hero alone must face the one who started the Great Cataclysm. If he destroys the Hero, the world is doomed to suffer at the evil one's hands.