Take a look at the example output from UberJumper's map viewer. The large, purple, angular structure on the left is the dungeon.
From what I've seen, it is a typical example. Dungeons start at ground level, run more or less vertically down into the rock layer, and then branch out, becoming mazelike. They may extend into the lower rock layer (where some lava starts appearing), but never into the underworld (where the sea of lava is). Dungeons are always underground, but are also always accessible from the surface.
Your spawn point is dead center in the world (horizontally, that is) and the dungeon spawns as far as it can towards either edge of the map (but never both; you only get one dungeon). This means that it is about as far away from the spawn as it is possible to get. Plus, you could always find you've gone the wrong way and be on the opposite side of the map. (If you find an ocean before you find the dungeon, you've gone the wrong way.)