I tend to do the continent/land mass first. Though you might consider where you want your rivers (if any are visible) you can always add the sea/ocean later as layers below the land.

There are several tutorials for creating world maps with PS here, Ascension's is quite good and there is a conversion of RobA's GIMP tutorial as well (can't remember who did it off the top of my head).