Mapping software
There are a lot of options out there for hex-mapping -
Illustrator,
the GIMP,
Hexographer, and
Campaign Cartographer to name a few. Here's where I stand on using each:
Adobe Illustrator is the most powerful, most expensive and most complicated of the bunch. Theoretically you can use Illustrator to do all of this, and do it nicely. Illustrator's price tag is $$$ and I'm not sure I even understand Creative Suite's pricing structure anymore (Illustrator is a part of Adobe Creative Suite). But the really professional looking maps are done primarily with Illustrator these days.
the GIMP is the Linux / free alternative to Illustrator. The GIMP can do 95% of what Illustrator can at about 0% of the cost. Very attractive.
Hexographer is software designed to make hex maps. It's java-based. I own a copy of hexographer and it does a pretty good job on small to mid sized maps. Larger maps tend to run into memory issues. I think that could be a problem down the line.
Campaign Cartogapher is another possibility. Supposedly pretty powerful and now easier to use, I'm just not a fan of its pallet. So I'm passing that one up, right off the bat.
Of the three remaining, I own and use all three (I own CS5). All three make basic maps fairly easily and I've started large mapping projects with each of them. As I envision this to be a living project, there has to be a certain flexibility insofar as I need to be able to add new base maps (you'll see why later) to my document. As far as I've discovered, hexographer can't do that. The GIMP can, but I also own a drawing tablet (a wacom 13") and I like how the tablet works with Illustrator better than how it works with the GIMP. Though this is not to disparage the GIMP in any way. I strongly suspect that if I had to use the GIMP I'd be very content.
As for hardware, I have a fairly modern gaming rig with a whole bunch of RAM, upper end graphics cards and dual monitors. Well, triple counting the tablet.
Design Strategy
Having had a considerable amount of experience mapping caves in real-life through Illustrator I'm familiar with concept of layers. Layers, as many will tell you, are crucial in dividing up and organizing your work. By placing each type of thing (hexes, political boundaries, rivers, etc...) in a different layer you can isolate them. Because you can also lock your layers you have peace of mind that you won't move something by mistake.
Lock everything except the layer you are working on is probably the most important rule.
I'm a little organic with layers. I add em' as I need them. Right now I have the following layers (from top to bottom):
Stolen Lands random encounters - to see where the random encounters plot on the map. I want to know if they line up after I've rotated the hexes (I'll explain later).
Hex Grid - just the grid.
Rivers - also lakes.
Coastline - goes under rivers and above hexes.
Hexes - the actual hexes. There will eventually be a layer above this for my personal campaign wherein I can alter hexes for things like farming.
Base maps - the maps that i'm using as source data. All resized to the same scale and oriented correctly. this takes some doing.
And here is a screenshot of what I've got so far...
Its the northern Stolen Lands and most of Brevoy. As you can see the hexes are re-oriented to have a northward face (the original hexes were about 19 degrees off). I did this because while the orientation worked for the AP, if we want to extend the map further we need to either re-orient the hexes or be forever bound to a left-leaning north arrow. I preferred to reorient the hexes. As I see it from a GM point of view the only real change is determining which hexes have which encounters. Aside from that, so long as you're not adapting an existing game, the change should be seamless. Existing games would have issues with kingdom boundaries and how hexes are developed.