Hexes? I don't understand, do you mean the witch ability, cause I don't see how that applies here... Or is it something I'm not catching on too.
He means a map of hexagonal tiles, which is traditionally used for wilderness travel.
Open world is a lot of work. Basically, you have to do about 3 times as much as you would for a more linear story, or improvise a lot - which in my opinion is not a good choice.
However, once you have the work put into the game, a lot of it sort of builds on itself.
I usually beginning by defining a small region - say a medium sized nation. I usually begin by defining a general geography (temperate mountains, desert kingdom along a mighty river, whatever) and an exotic speculative government - only octogenerians are allowed to vote, a hereditary queendom, a council of philosophers, a group of vampires, a literal plutocracy where you bid to create the laws, government by the ghosts of your ancestors, etc.
Then I list every plot and bit of intrigue or danger that the nation is undergoing. That usually involves about 16 sentences that are going to become my plot hooks. Just go wild brainstorming who hates who and why, and whose out of power and wants in it, what those in power are trying to get away with, and what madman are trying in dark and secret places. This could be anything from 'X wants to become an officially recognized state religion', 'A scary half-mad sorcerer wants to breed an army of owlbears', 'Ousted family believes it is the legimate claimants to the thrown', to 'Duke X is a serial killer.'
I then map the region at a very high level. I then think of all the dungeons, legendary monsters, greater spirits, unusual creatures and so forth that are living tucked away in different corners of the nation - wyverns in that stretch of mountains over there, a fairy wood, tribes of goblin bandits, a triple normal size dire boar over here, a plague of perytons, a sea hag, a sea dragon, a family of storm giants off shore, nomadic elves, a village of wereboars, the former lair of a defeated dracolich, a village inspired by Shadow over Innsmouth, the ruins of abandoned cities, castles, and temples of an earlier nation of a different ethnicity (the former rulers are now an oppressed minority). At this stage, this is all just ideas. I have no idea how or if any of this will play a role in the campaign. It's just the color of the region, and inspiration for deeds of daring.
I then briefly sketch out the neighbors with a couple sentences each and give each a name - Friendly relations with the peaceful kingdom to the south. Long standing rivalry with the militant nation to the north. Some contact with the dwarves in the mountains to the north-west. Profitable trade with the larger nation in the continental interior.
Once I have a plan, then I just start filling in details, starting with what I think I need immediately and moving from there. I also like to have a couple of 20 page wandering encounter tables written up with stat blocks, lists of pregenerated names of NPCs of that type, and so forth that give me a feel for what's around and help with improvising if the PC's take a journey. You can use that sort of thing both to brain storm in game, and to buy yourself breathing room to stat out things ahead of the PC's get there. The important thing with random encounters though is as much as possible, tie them into those hooks you brainstormed earlier or into the PC's background. BTW, insist on the player's writing up backgrounds. That will help you know what you need to detail regarding the setting and will provide fodder for ideas about what is going on that you wouldn't have thought up on your own.
If you expect a lot of wilderness travel, make a more detailed map with ideally 40-60 planned encounter locations and multiple regionally specific wandering encounters. Again, wandering encounters should serve to tie the characters to the details of your world, so if you roll 'Bandits' you can make a good guess at what sort of bandits you need, where they lair, and who supports them. Are they just a few desparate out of work mercenaries trying to make a living between wars, or does a particular village wink and nod at young men robbing 'foreign' travelers? Or maybe their is a bandit lord in some hidden hold in the woods? Maybe the 'bandits' are actually supporters of an ousted ruler, and they pretend to be collecting a tax for the restoration of the rightful monarch - perhaps they even believe it. And so forth.
If at all possible, start in a fairly rural and low population density area. Very large towns are nightmares in open world. Each large town is a separate open world project unto itself, and I never quite finish any of them to any reasonable standard.