As requested, here's my technique for making random maps of places that don't exist. Note that I don't currently have an art app with the needed features, so I can't post screenshots or anything. So if I'm unclear about something, just let me know.
How To Make Random Digital Maps (guaranteed to have no straight lines!)
- an airbrush tool that spews pixels with hard edges (blendy edges will mess you up later)
- a fill tool
- an undo feature
1. Using the airbrush tool, randomly squiggle around the whole drawing space alternating between black and white, until the image resembles snow on a TV. There should be more or less equal amounts of black and white, but it should look random rather than uniform.
2. Switch to the fill tool, and select a shade of blue suitable for water. Click somewhere you want to put water. If it fills up half the screen, or only fills a couple of pixels, hit undo and go back to step 1 and fiddle some more before trying again.
3. Once the b/w mix seems OK, use the fill tool to make your oceans. It doesn't matter if you fill black or white areas (and I always do both at some point)...as long as the oceans make shapes you like. Remember, undo is your friend!
4. Once your oceans are done, you can color in the landmasses with grass and desert and mountain and forest colors in the same way. (Mountains can be tricky though, as you can rarely find a place where it wants to do long narrow bits, heh.) Pop in a few lakes if you can find suitably sized areas. Don't forget to use undo if you get something wonky!
5. Now that you've got your land and your oceans, it's time to remove all those leftover black and white pixels. You can start with any place you feel like, just keep in mind that the areas you do first will get bigger. Anyway, all you have to do is alternately fill an area with black and white until all the random excess pixels are gone. (This is why a blendy airbrush doesn't work...most of the things you need to take out would be various shades of gray, and thus very annoying to get rid of.)
And that's basically it!
Of course you'll have to draw in rivers by hand, but squiggly lines aren't that hard to make.
If you have textures that look like desert or forest or whatever, you can fill in appropriate areas with them if you want to. And of course you can add names to stuff. But that's just icing on the cake.
Enjoy your mapmaking!