Hi,
This site...

http://realpolitik.sourceforge.net/Variant_Creation.html

..will tell you everything you need to know technically, on building a Realpolitik Variant.

For designing the map, I would suggest you use an art program that supports layers. Illustrator, Corel, Paint Shop, most of them support such, but MS Paint does not. I use an old version of Paint Shop Pro which works just fine.

Layers you'll need to be able to turn on / off...

Base layer (transparent)
White layer (white)
Borders layer (black lines making up the country borders)
Tan and Blue (shade countries tan, waters blue)
Texts (any flavor text or space names)
Artwork (any original art in the frame, etc)

This way you can turn on just the white and black layers (possibly text layers too, to exclude text from the shading in RP) to save a black-and-white borders image, which is the first thing you need to make an RP variant. Then later you can turn on the colors, texts, and artwork to save the colorful bmp that you'll need as the last step. When you have those layers and you can export a good b/w image, then you can start the tedious RP process of defining the map and region files, per the above link.

Many folks have made variants here, so just ask any questions and I'm sure you'll get feedback.
-mike