A map of some of what the first floor would look like without any rock.
The Stoodeep Mines is a huge mine, with several levels, accessible from all the nations. Navigating can be difficult because it is very dark and completely blocked by rock (although other players have most likely used a lot of bombs to open up paths).
On the second level you'll find a phoenix, and an iron gate that will return you to the first level of the mine.
Even further down you will eventually find a Zaap, and the high-level Elite Riktus dungeon.
Very deep down there will be exits in four locations, one for each nation, no matter matter which one you came from. Look at the world map (before you enter the mines) to learn which direction to go for each nation, as it will be the same in the Stoodeep Mines as it is on the world map.