I'm not a veteran but I'll throw in my 2 cents.

1. Determine size
2. Sketch map on graph paper, just rough outlines
3. Scan in and trace in Photoshop (zoom more when tracing to add more detail)
4. Add grid line, legend, all that stuff
5. Analyze where I want mountains (they determine where everything else can be)
6. Think about the basics of climate to determine where other things can go
7. Place rivers, marshes, forests and deserts
8. Add place names
9. Clean up map (erase grid lines that I don't want etc)