Hey Kentharu, I was about to post this:
Its kinda complicated
The basic outline of the continents and oceans etc is a separate GIF image that I made in a standard image editor type program. Ive then been doing the rest with the macromedia Flash editor (its free to download, but only lasts 30 days or so unless you somehow get around that

). If you havent heard of Flash, its a browser plug-in thingy behind most of those cartoon-style animations and games that you can play through internet explorer etc. The editor is separate to download. Its obviously set up for doing animation and interactive stuff, but I find the basic drawing method is very good for creating a map. Every line that you draw is click-able and moveable, and can be bent into different shapes etc. Really handy for doing borders, and its really easy to change the fill colour of provinces also. I never have to change the background image of the land and oceans, all the icons and names and provinces are on separate layers on top of that background.
It can be a real pain to get it to output the map in a standard image format, since its not really designed for that. Ive had loads of errors like bits of the map randomly switched around and icons being replaced with white boxes in the final image
but seem to have got it working for now.
/edit - in short, ive found it good to use, but it will take a bit of patience and experimentation. Also really need broadband to download it (about 50 megs or so IIRC), which i dont have anymore, so i hope it keeps working...