I was asked how I made the coloring on my map in this other thread ( http://www.cartographersguild.com/showthread.php?t=6054 ). So I've thrown together this short tutorial.
Of course, I developed this technique, while trying to emulate Ascension's Antique-style maps in Photoshop, so props definitely goes to him.
Now for the tutorial:
1: First you gotta have a landmass. I this case, I made a fractal shape using CC3.
2: Then we paint it black, or any other color, as long as it is a single color with a sharp edge. We'll keep this one around as our definition between what is land and what is sea. Name the layer "Land/Sea Solid".
3: Next we create a new layer. This is where we will define our country borders. Call it "Countries Solid" and make sure its above the Land/Sea Solid layer. Then we paint our country borders in different colors in this layer. Use the pencil, we don't want blur at the edges. And no need to worry about coastlines. Just make sure that you don't use the same color at two neighboring countries.
4. Now go back to the"Land/Sea Solid layer, and select the sea with the Fuzzy Select Tool. Choose the Countries Solid layer without removing the selection. And press delete. Voila, your borders now fits the coastlines.