I'm astounded when I see maps that artists and designers are creating these days, like Jason Engle who does many of the maps for Wizards of the Coast. I use Photoshop (CS4) for most of the graphics I make. Sometimes I use Painter for softer painterly images, or rarely I use Illustrator for hard graphics.
To create a fantasy map I use this common photoshop technique:
Open a new file 8.5" x 11", 200 resolution, RGB
Select Filter: Render: Clouds
The result will look something like this:
Next, select Image: Adjustments: Brightness/Contrast
Set contrast to 100%
Slide brightness back and forth until you get shapes you like.
This will create convincing looking coastlines. The result will look something like this:
I see the white as land masses and black as oceans, you can reverse this if you like by choosing Image: Adjustments: Invert.
I do these steps a few times until I get land mass shapes I like, and then crop into the most interesting area using the Crop tool.
Here is the shape I've settled on with the "Lavivrus" map over layed so you can see how I'll be fitting it in:
Next: creating terrain.