I've been working on my very first world map and this was my progression:

1) Land shape (with a base texture) and a basic background/ocean colour
2) Mountains next.
3) Then the rivers (just a placeholder layer that was tweaked several times as the map developed).
4) I then started adding terrain textures and the trees (which were also tweaked and added to along the way).
5) Then the initial roads/paths and symbols (also added to along the way).
6) Once I got a better idea of the terrain colours/textures, I added a background/ocean texture and adjusted the colour to match.
7) Then I started adding the fancy stuff, like the border, cartouche, legend, compass rose and rhumb lines.
8 ) Once the terrain was completely done I redrew the rivers properly.
9) Then a lot more tweaks and revisions to many of the different elements.
10) And now I'm getting ready to do the labels.
11) After the labels there will probably be several more last-minute tweaks and touch-ups before I finally call it done.