So, the PCs are all eager to head into the wilderness. You've got it mapped out, you have your random tables at hand, and you're ready to rock-and-roll.
Traditionally, the most defining feature of a hex-crawl is resource management. The further the PCs get from civilization, the better the rewards and the cooler the encounters. But the further they also have to go to replace consumed supplies, destroyed equipment, and lost mounts and hirelings. There's an obvious solution to this problem: the PCs can get their supplies from the monsters.
Sure, they can pillage and plunder their way across the landscape, but that only works so long as they encounter groups that are relatively easy to defeat in battle. And that's not what I'm talking about here.
my goblin tribes are 200 to 600 individuals with fairly advanced neolithic tech. But they sell the PCs arrows, mounts, and food, while the tribe's shamans can provide extremely basic (ie levels 1-3) magical services.
Once your players have made that leap, things can get really interesting. Clearly, there's conflict between the various monster groups on the island I've mapped out. In the east, we have goblins vs. lizardfolk vs. orcs vs. bullywugs. But there's no reason you can't make it more granular. Maybe the individual goblin tribes don't always get along well. As the old saying goes: me against my brother; my brother and me against my cousin; me, my brother, and my cousin against the stranger.
A variation on Zak's Connections Between NPCs Diagram from Vornheim is great for this sort of thing. You can scale it up for allied nations of villages, or down to cliques among the females in a single village.
Generally, you want to move from the micro to the macro in this. In the first village the players attempt to deal with, maybe they'll get involved in a fight over the chieftainship of the village. After that, they could improve their relations with the new powers-that-be by championing that village against another. And then help cement an alliance of goblin villages to thwart raids by lizardfolk slavers...
For your part, don't be thinking more than one or two opportunities ahead. Scatter a few opportunities before your players and let 'em play with the ones that interest them. It's usually not worth it to try to guess what the players will do; they'll frequently surprise you. Look at what happened, who benefited and who got a bloody nose, and build the next set of opportunities on that.
And always keep an eye on the horizon. Who are the monsters the players are dealing with dealing with in turn? How can you draw the attention of the players out towards the next line of hills, across the next river? You're weaving an interconnected world here, not telling a village-of-the-week story. Always be tossing out links to the big picture, or having macro concerns affecting micro challenges.
Art by Arthur Rackham.