There is no specific order to visiting this dungeon. Here is one of the best routes according to me:
Equip the Lamp, this dungeon being often plunged into darkness. Go right, place a bomb against the cracked wall to the north and go on. Open the chest holding only 5 rupees, then go back. Go to the other side of the room, place a bomb near the crystal switch, then run to the platform to the south and move onto it to cross the pit. Next throw a bomb upwards, in front of the window to the right so that the light may shine inside the room, which unseals the door. Continue north.
Move to the far north, then go left and walk on the floor switch which causes a key to fall. Turn into a painting, go left, then when the beams head towards right (and that you see a glow at your feet), exit and get the Small Key. Go back north and place a bomb on the cracked floor so that the light can go through. Unlock the door on the right.
Climb the steps down on the right or on the left, then merge into the wall to cross the long hallway and avoid the large rolling iron balls. Go right and take the path east.
The enemies move in the direction opposite to yours. Get rid of the two green enemies, then place a bomb on the floor and move so that the red enemy gets close by. The platform activates once the enemies are defeated. If you wish, you can recover a few hearts by merging into the walls. Move onto the platform and go south when it is down! Go southwest, light the brazier to see better, then open the nearby chest which holds a monster tail. Place a bomb on the cracked floor in the northeast corner, and drop through the hole.
Open the chest which holds a monster horn, then turn into a painting, go left to the next corner, then exit and pick up the Small Key. Use the map to guess the path and head northwest. Take the northwest path, then walk up the stairs to the north to go back to the...
Go back in the room to the east, move onto the platform-lift, then place a bomb against the opposite cracked wall, and go on. Walk on the metal walkway to the south, open the chest to get 50 rupees, then go back in the previous room and take the west path.
Go to the far west, merge into the wall and go right until you are near the crystal switch being in the east part of the room. When your energy gauge is full again, leave a bomb near the switch, then quickly, merge again, go left, exit near the switch to the west and strike it before the first one deactivates! A chest appears to the south. Merge once again to emerge north, move onto the platform-lift, go south and open the chest to get the Compass! From the south part of this room, place a bomb on the moving platform when it's up so that it blows out when the platform is down. Move onto the platform and go south when it's down to arrive in a room with small fairies. Take some in your bottles if you wish, then go back in the previous room and leave through the northeast path.
Climb the steps up and unlock the right door.
Light the right brazier, then strike the crystal switch which makes two wall segments spin around. Next, place a bomb near the switch, then quickly stand against the right wall to go right. Place a bomb on the cracked floor to the south and drop through the hole. Once on the first floor, open the chest which holds 50 rupees, then go back to the second floor, where you dropped, and continue east.
In this room, the floor disappears after a few seconds, you must therefore act quickly. Move to the centre, use a bomb and throw it to the left near the above switch, then walk quickly to the south and go through the door which is now unsealed. (If you were too slow, merge into the wall to go back to the previous room and start again.)
Turn into a painting on the wall just opposite, go right and exit near the chest (on the east side of the room). Open it to find some monster guts, merge again into the wall, then continue right and exit further. Go to the centre of the room, stand on the south platform-lift and strike the nearby crystal switch to move up with this platform. Merge into the wall, then go left (and recover a few hearts) and exit on a high platform. Slash the two skulls to find an energy potion, then place a bomb in front of the two obstructed windows to see three light beams point towards the basement.
Go back to the centre of the room. If necessary, strike the crystal switches so that the two platform-lifts are down, then place a bomb near the south one, quickly stand on the north platform, strike the switch to go up and stick against the wall which spins when the bomb blows out! Open the big chest which holds a Master Ore! then activate the switch to go back in the previous room. Then, go in the southwest corner, throw a bomb up onto the metal grid to clear the window and also see three beams of light pointing towards the basement. Next, go back a little to the right, place a bomb near the south switch, then run left and stick against the left spinning wall when the bomb blows out! Light the brazier to the south, pick up the 16 blue rupees and the red one, then use a bomb near the switch in this secret room to make the wall spin again. Go out through the northwest path.
Here, as in the other room, the floor falls down after a few seconds. Move simply to the north and exit northeast. Place a bomb near the cracked floor and drop through the hole. Once on the first floor, put another bomb on the cracked floor and jump.
Pick up the red and blue rupees, then drop yourself below and take the stairs to the north to come back to the first floor. Climb the steps down on the right, take the narrow hallway to the south, place a bomb on the cracked floor and jump through the hole.
Pick up the Small Key, light the nearby brazier, then jump lower. For 30 additional rupees, you can place a bomb against the cracked wall in the southwest corner and walk under the raised platform, and do the same in the southeast corner. Take the path east.
Walk straight up to the brazier and put it out using the sword, which causes the paths to appear. Head south. For 50 additional rupees, head southeast, place a bomb against the cracked wall and take the rupees under the platform. Next head southwest and take the path south. Go to the far south and unlock the eastern door.
Again, the enemies move in the direction opposite to yours. Make sure that they fall through the opening in the centre, then strike the two green enemies with the sword. Next, place a bomb on the floor and move around so that it blows out near the red enemy. A warp portal appears and the platform activates. Go out through the southwest path, cross the large room westward, then go north and enter a dark room.
Start by putting out the brazier using the sword, then head to the other side of the room by turning into a painting and sliding through the gaps in the walls inside the room. Stand on the floor switch hidden under a skull, which makes a chest appear, then go south to open the chest containing a Small Key. Now go back southeast into the previous room, go south and unlock the door.
Take a few steps and watch the light beams. Light the brazier to the north, then go to the far south and look left. Throw a bomb to the left so that it rolls along a slope on to a switch which it will activate. Next go onto the moving platform and throw another bomb along the middle slope to activate a second switch, then throw another bomb along the northern slope to activate the third switch, which causes a big chest to fall. Open this chest to get the Big Key! and go back towards east.
Cross the room again eastward, take the southeast path, go onto the platform-lift and go out west. Turn into a painting, go right, exit on the next platform to gain some energy, then continue right towards the next platform and exit. Strike the switch, which raises a platform on the right, and activates an eye switch, which opens the big gate in front of the boss door. Drop yourself below, go near and unlock the boss door.
Light the two braziers so that the boss appears. Let bombs on the floor and try to attract him to them. After three or four successes, his mask shatters and reveals his weak point. Keep using bombs or striking this weak point with the sword. When he blows the flames, run to light the braziers again and continue slashing his red point until he is defeated!
Next, get the Heart Container, then touch the painting. Gulley is also one of the Seven Sages! and he asks you to help the other ones. Enter the portal to come back outside of the palace.
After having completed Dark Palace, the soldiers outside have disappeared. You can then look for the Piece of Heart and the maiamai if you didn't get them previously.