Mapmaking help needed

[Super Missile]

As I play nation games a lot here I decided some map making skills would be useful. Now I use paint.net (I just change the color pixel for pixel, of course that's hideously slow).

Does someone here have some tips, about which programs, methods, etc can be helpful? I'd really appreciate it.

[Color-Copycat]

GIMP2 is pretty good. It can handle layers, which is of inestimable help. (basically you can draw on multiple canvases that can be simultaneously superimposed with varying transparency values. Handy for doing political orders on one layer, rivers on another, etc so that they can be kept conveniently separate while you work on the map)

[Super Missile]

And can you also work in grids there?