From: Eindhoven, the Netherlands
Both ways work.
You can use HexDraw using the templates provided here. Then you'd paint your maps in HexDraw, scale the map to the right size as described by the Mod guide, scan the map in the Map Values editor, and fix some hex values where necessary. It's straightforward but laborious, and you might need to buy the full HexDraw application as the demo is limited to a small map area.
Alternatively, you can try to master QGis as described by the pinned QGis map creation thread. In QGis, you can use digital elevation data (saving a lot of manual work, compared to HexDraw) and paint roads, waterways, towns, forests, etc. on top. It's more complex, but can be a lot faster, especially when you want to make changes to your map. At the end, you have a bitmap that's great for being scanned by the game, but not as pretty as HexDraw's. To use a pretty map, you can use QGis to clip the same area Google/OpenStreetMap/Bing map, or you can PhotoShop something pretty. Or you try contacting me to render a pretty map for you given the QGis created bitmap.
What map do you have in mind to create?
OTS "garden boy"