To do a proper job of making a map, you'll need a few tools. Sure, you could try to draw a map pixel by pixel using Microsoft Paint, but you'll end up wanting to kill yourself, and odds are good your map will not look very good.

At a minimum, you'll need a decent graphics editor. You'll also probably make use of a good online image search engine, some fonts, some stock imagery, and depending on your image editor some powerful plug-ins. This tutorial tells you about a few of these tools and shows you where you can get them.

Graphics Editor

I use Paint.NET; because it is powerful and free. Paint.NET is probably the most powerful and fullest featured free graphics editor available. It's 'layers' functions will be one of your most important tools in making beautiful, functional fill-mode maps. It's abilities are expandable by user written plug-ins.

You can get this program at:

http://www.getpaint.net/download.html

You'll also be wanting plug-ins. Plug-ins are pre-programmed image editing effects that make Paint.NET incredibly more powerful. These include tools to automatically outline shapes, cleverly blur background images to save memory with minimal distortion, to adjust colors and transparency, and more. You can find those in a forum at:

http://paintdotnet.forumer.com/viewforum.php?f=16

There is a plug-in Index thread that lists all of the effects stickied near the top. That forum also includes a tutorial on how to install your plug-ins.

Other popular options are GIMP (another free downloadable option), Photoshop (an expensive, but powerful choice), and Pixlr (a free, fully online image editor).

Fonts

Fonts add a lot of character to the text you may use in your map image. Also, using a Dingbat font can save a lot of time if your map uses some sort of icon to denote a territory.

I get all my fonts for free at dafont, which has all free fonts. Be sure to read the license granted by the author of each font. There are plenty of other options for pay and free fonts which you can find via a web search.

Take care as you install font files; I have picked up a computer virus or two from other font sites, but this one seems to be pretty clean. You'll have to figure out for yourself how to install new fonts on your particular operating system. If you have Paint.NET open when you install the font, you'll have to restart the program for it to recognize the new fonts.

Search Engine

You'll be wanting to use this to find images to edit or trace for your maps, in case you don't intend to draw one totally from scratch. You can use the web search to browse through dozens of interesting or strange maps blogs and websites. You can also use an image search to look directly for images you can turn into fun boards or maps for Wargear.

My personal favorite image search engine is Bing, which provides a great breadth and depth of results on a single scrollable page (no "Next, Next, Next..." pages to browse through 20 or so images at a time). It also allows you to quickly sort your results for B&W vs. Color, photo vs. illustraion, and more.  Google tends to yield broader results based on a single search term, but has few tools to further sort those results and seems to lack some of the diversity of results that Bing provides. As with fonts, be sure to check for copyrights and other usage licenses for your images if you find them out on the world wide webz.

Additional Resources

Wikimedia is an online source for free, public domain images. If you want to be absolutely sure you don't need to worry about copyrights or usage, look for your images here. If there are license issues with an image served on Wikimedia, they make it very clear what you can and cannot do with an image.

Mayang has tons of stock imagery and textures to use for background and frames on your maps. Textures come in plenty handy when you want to add some character to a board image.

If anyone out there wants some pointers on using GIMP, just shoot me a PM.

This has been added to a Help page http://www.wargear.net/help/display/Board%20Design%20Tools (Awesome write up Cram!)
Any objections to unstickying it?