No paper for me. I get the basic ideas about the stage in my head, a general concept of how the stage will be mapped, and whether it's retarded or not in my head, and then get to work on the thok barrier.
As for the wad itself, I get the textures and basic sectors up first, then I get to work on the header, vital thing types, and sector/linedef types. Then I get to work on minor details, such as scenery things and background scenery.
Not that I make maps very often. While I've started quite a few, I only have two that have actually been completed. :\