For the most part, the difficulty on this depends on the tools you have available, whether you plan to publish the maps, and how accurate you want everything to be.

The simplest technique is to use a map in an existing atlas or online map source such as Google Earth and zoom to your area of interest. Then, download a "hex grid overlay pdf free" (search for that in your favorite search engine and pick a result such as https://incompetech.com/graphpaper/hexagonal/ or https://madisonpaper.com/hex-paper/ ) overlay. Finally, assemble the hex grid overlay on top of the map using your favorite image editing tool. The hard part is scaling the hex grid to the map, but if you have some notion of distance in your map (like a scale bar), you should be able to figure out how to stretch the hex grid to match it.

If you look at the original assumptions, the most limiting one is probably the "what you want to do with this map" one. For publication, you'd need to pick a map with permissive licensing. If you don't want modern roads and such, use a data set like Natural Earth. You'll need some way to project that data into a suitable map projection (Google Earth does this automatically with its data, which is why I mentioned it earlier - there are many tools out there that could do this with arbitrary data) like Orthographic (because it sounds like you're interested in relatively small areas on the globe) to get your base map.

If you have any questions about my 20 second firehose above, please ask!