(The following is from memory. I haven't played Arena in a long, long time.)
It'll be in a chest that's placed on the last level of the dungeon where the stairway to yet another level would be placed if there was one. Always. With a mage character I used to go there in a straight line through a custom
passwall spell: three passwall 10 effects in a row, resulting in a 30-block remover.
Good times, good times.
Anyway, you should notice that in those random dungeons, the stairway tiles are about at the same place. In the most frequent dungeon type (from what I remember), they were both straight in the center vertically speaking (north-south map axis) and about in the quarter and three quarter position along the horizontal/east-west axis. When you get out of the west stairway, head straight east; and inversely go to the west when you're on the east stairway.
On the bottommost dungeon floor (or topmost tower floor), instead of a new stairway, you'll find in the special tile a chest. Open it, and you've got your map.