Oh how I love hexes.

[DrPraetorious]

Oh, how I love hexagons.

Mediafire link since attachments are still busted:
http://www.mediafire.com/?1zioy2hufv1

Here's a map with a hexgrid laid over it. Maps like this are pretty easy to make because the auto-border parser has no trouble finding adjacency on a hex-grid.

Here's how to make one in GIMP.

0) Copy my hexgrid into your patterns folder for GIMP. On my machine this is: F:\Program Files\GIMP-2.0\share\gimp\2.0\patterns

1) Draw your map (no borders or province dots obviously.) This is set up for wrap-around maps, you'll have to manually delete province dots at the edge if it's not wrap around. This one is easy wrap-around, I just took an existing map and reflected it over the central axis twice.
2) Scale the map (Image->Scale Image) to be an exact multiple of 206x177. Alternatively, you can scale the hexes in hex_extended.pat (it opens in Gimp) but make sure that the white dots are still in the right place. Also, these hexes really are the right size for dominions to look good.
3) Select the entire map (Ctrl-A on a windows machine.)
4) Select the paint bucket tool. Set the Opacity slidebar to 100%, set Mode to Normal, set Fill Type to Pattern Fill. Click on the pattern and select the hex_extended pattern. Set the affected area to "Fill whole selection" and click.
Anchor the new layer, save the .tga file (with a new name) and tada! you've got a hex-grid laid over your map.