I don't know the look you're going for, but The Gimp should be able to tackle about anything you need. While most of the tutorials on the CG site are fantasy-map oriented, if you're just starting with The Gimp maybe dipping into a few of them would help you get some general proficiency with it.

For your game, can you describe what you need the map to do for you? Are there any maps online you can point us to that typify the aesthetic you are shooting for?