I love hexcrawls. The feeling of discovery and exploration and finding cool things in the world is why I play the game.
I use a lot of hex crawl elements in my current campaign (which is a mix of dungeon delving, some focused adventures and hex crawling... lots of variety).
My basic approach is to have thematically defined regions or areas. These areas should be unique and evocative and present a strong choice. I have each region focus on a set of typical denizens and locations. Players can (by exploring and becoming exposed to the encounter tables) start learning about a region and prepare for it. I have set piece locations placed in hexes to be discovered. These are either small interesting points of interest or smallish dungeons (maybe 4-6 rooms).
In addition to placed locations, I've been developing a procedural content generation system for hex crawl locations. The purpose of which is to fill in the blanks with unexpected and interesting features and situations.
My procedure works like this:
1. Roll per hex for Encounter, Special Location, Special Hazard. Each region will have its own chance in d6 for each (some regions will have more encounters than Locations; others will be more hazardous). It will be possible to have both an Encounter and a Special Location occur at the same time (improvise to figure out the situation).
2. Encounters are rolled on a bell-curve encounter table for the region. There will be a set of 'common' monsters that will give the region character. The extremes of the curve are for important or powerful beings in the area. I try to add beneficial encounters at the top end. That way, if the players start clearing out the area, I can start rolling encounters with a bonus to the roll.
3. I use
Retired Adventurer's encounter rules. When an encounter is rolled, I roll for creature, lair, tracks, spoor, or traces. Creature means they encounter the actual creature. Lair means they encounter the creature in its lair. Spoor means the creature is close by (the players can encounter it or avoid). Tracks mean the creature was close by (the players can track it to its lair, or avoid). Traces mean the creature was close by some time ago (the players can learn of the existence of the creature). This gives players more choices and information without every encounter being a fight.
4. Reaction rolls (borrowed from B/X and OSR games) are used when there is an encounter. Not all encounters are fights. Sometimes players encounter helpful creatures or at least can negotiate with competing intelligent factions.
5. If there is a placed feature in a hex they enter, they encounter it (unless it is particularly well hidden). I'll generally have each hex have anywhere from 1 to 6 features (I use 6mi hexes). Other features can be searched for and will have an assigned search DC. Players can also survey a hex with Survival and get a count of number of features.
I have a library of locations and encounters saved up (great resources:
One Page Dungeons,
Hex Crawl Chronicles,
d30 Sandbox Companion ) that I can draw from. If I generate a Location, I'll roll or pick something. Once the location has been rolled up, I place it in the hex and there it stays.
The point of this procedure is to try to create meaningful choices. Hazards can be avoided if they take the long way around (lose valuable time), monster encounters offer choices to avoid, track, or parley. Locations can be explored or sometimes they can just note it on the map and keep going.
Usually the players will have some goal in mind, but sometimes I've seen them abandon that goal when they encounter an interesting thing in the hills. Sometimes, an unexpected adversity weakens them and they have to abandon a mission.
I've been running and tweaking this with 5E and Basic B/X. I've been able to run entire sessions improvised based on the results of the procedure.