STEP THREE: LAND HO!
I'll start the map by hiding the two color layers I created (background & color sketch), and then turning the opacity of my Sketch layer down to about 20% so as not to distract my work.
I could make the land in many ways, the most useful being creating & saving a "path", which gives maximum flexibility later on; but using the vector tools in Photoshop is tricky & I want this tutorial to be completely straightforward, so for I'll go plain-Jane here The method below was how I made my first maps in PS, and it was easy, and it worked just fine.
Create a new layer on top of all others called "Land." In that layer, using the base color I chose for the land, I outline the islands with a medium sized brush (around 5px), & then color them in. (See image below).
Next I use the magic wand to select anywhere on the colored landmasses; the "marching ants" should appear around the islands. Leave them marching for a minute.
I now create a new layer on top called "Land Outlines", & I choose black as the foreground color. Then in that layer I Edit>Stroke, choosing about 4 px. wide, centered, 100% opacity, & normal blending. BAM! The islands are outlined. Nice, eh? (see image below)
WATER LINES
But let's add one more fun detail: fancy-schmancy water lines. While my ants are still a-marching from my last action, I create a new layer called "Water Lines", then Select>Modify>Expand about 4 px. The ants should now surround the islands. Now I Edit>Stroke just as before, but this time at 1 px.
I do this Expand / Stroke action again and again, each time expanding more. When all done, I Select>Deselect (or, Ctrl-D), which "turns off" the ants.
But I think I'll go just one step further: in both the Land Outlines and the Water Lines layers, I Filter>Distort>Ripple at about 115 - 125%. Why? Mainly because I like the variations in the line widths this gives. You don't need to do it at all. A downside is that it may require some touch-up of the land &/or the lines themselves, though; but worth it, I think! (see image below)
Note that there are plenty of other options to create line variations; another nice one is to select the "Dissolve" layer style (from the pull-down menu just under the "Layers" tab), which gives a cool "fuzzy" look.