There are two basic kinds of hex maps:
1. hex-grid overlay
2. hex-grid tiling

The first's a simple map with a hex grid op top that you use as a measure of distance. The second has its elements contained within the hex-tiles.

You should also consider how you will use the map, most importantly whether it will be a digital, interactive map or a fixed image.