1. Decide or Guess Which Kind of Traveling Your Campaign Will Be About
There are basically two ways to use a sandbox map in a campaign:
A-PCs usually have objectives (of their own devising or given to them by interested parties) and these objectives take place largely in locations the GM has some concrete or prepared ideas about and the PCs cross the map to get from one place to another and any stuff in between objectives is either an obstacle or a (perhaps rewarding) distraction.
B-For the PCs, looking carefully at what's in each bit of the map is the adventure. i.e. This is a true hardcore hexcrawl, where the PCs search each bit to see if there's any loot or whatever in it and that's mostly what they do.
These different kinds of situations require different kinds of maps.
Also, if type A, try to guess if your PCs will probably mostly be riding or walking.
2. Find Two Places In Your World Where You Can Decide How Far Apart They Are If you're interested in realism at all, an important concept is how far you'd have to travel before encountering a different culture. The further back in time you go (and thus the further back you go technologically) the closer places can be and be totally different. Also if you plan to have a lot of big geographical barriers like seas or mountains everywhere between places then things can be closer together.
Here are some numbers from an old post:
Excluding island nations, (western) European capitals are generally at least 500 miles apart. This is a base number for figuring how long you'd have to travel if moving from the center of some empire to the capital of some other empire...This means getting from a big city to a really different big city takes a long fucking time, in game days, or at least requires crossing some famously dangerous or inconvenient geographic obstacle. -The distance from Ghent to Antwerp is about 4o miles, from Rome to Naples is like 140 miles. These are minimum distances for going from a big city to the next biggish city where they speak whatever the locals call "common"... Castles are more densely distributed than cities, of course. Depending on what you consider a "castle" and what source you consult, a heavily fortified country like England had a medieval density of like one castle every 6-10 miles.
3. Decide--Timewise--What The Density of Incident-While-Traveling In Your Game Will Be
Now: People have a wide variety of opinions about scale for sandbox maps. So many that I could, with minimal effort, have linked to one article about how wide someone thinks hexes should be for each word in that opening sentence if I weren't so lazy. Hex scale in a map is not actually mostly about how far things are from each other or how long it takes to travel across a kind of terrain (forest, scrubland, etc.) before it turns into another kind of terrain, it's about how often something happens while PCs cross terrain. And what are PCs doing while "crossing terrain"? They are having a chance of randomly running into something that they didn't know was going to be there.
The real purpose of a hex (or any other series of regularly-shaped compartments you divide your map into--though hexes have certain advantages) in an RPG is to demarcate the point at which the PCs have come into the orbit of some new and interesting thing.
In real medieval life, though travel was dangerous there were absolutely zero ogres in the woods waiting to grind your bones to make their stew. Jack Vance had Cugel running into a new terrible thing every ten minutes, whereas other adventurers in other stories could wander for weeks without incident. Point is: density of encounters is really an arbitrary decision about the kind of fiction you're creating.
If your campaign will probably mostly involve traveling Type A, the size of a hex therefore indicates the rate (in game time) at which the PCs enter the orbit of unexpected, interesting things and also how many of such things will be encountered on the way to any given place. So look at your two places and the distance between them--approximately how many incidents would you want the PCs to encounter on the way from this place to the next? Assuming a 20 miles per day ride and 10 mpd walk, how often is this: approximately every (game) day? Every few days? Twice a day. Once every six days? Decide.
(If you imagine a world where you can basically always get from one pretty-much-prepared adventure locale that the PCs know is there without anything happening to another without that much happening then you don't need hexes. You just need a way of measuring distance between points so that you can say how many days provisions they'll need to cross the territory.)
If traveling mostly Type B-style, the purpose of the hexes is to determine how long--on average--in game time it will take to search an area and find out if there's anything interesting in it.
Remember, either way, that this is just an average. If you want to do something like have the density increase as PCs get further from civilization you can worry about that later.
18. Decide Incident Randomness Level
Let's say you've decided on a density-of-incident of 1 incident every 3 days. You can express this one of 2 ways:
First way: you can have large hexes that always have something in them and take 3 days to (type A) cross or to (type B) search, so, like clockwork, no 3 days will pass entirely quietly. The danger level of traveling any distance is easy for PCs to calculate.
Second way: You can have twice as many hexes (smaller hexes), each of which takes a day to cross, but the table you roll on to see what happens in the hexes indicates "no encounter" half of the time.
In both cases you have an encounter on average about once every 3 game days but in the high-randomness option the whole thing is much "swingier". You might travel 10 days from Barrowhall to Flugsinchubble without incident if you're lucky.
Decide whether you want things at more regular intervals or more random intervals. This randomness is a percent. 50% randomness is a lot of rolling and getting "oh look, nothing" 10% isn't. Pick a randomness level.
19. Decide Hex Scale
Assume an average movement rate of 20 miles per day riding and 10 walking and 3 searching (if you think you have better numbers, use them--if your campaign is mostly desert or steppe it might be 30/15/5) and keep in mind the density-of-incident numbers and randomness level you just decided. Make hexes a size that fits that.
Some people like equations, so here you go...
H = DN - P(DN)
Hex size = [ (Distance traveled in miles--for type A campaigns---or area searched in square miles--for type B campaigns-in one day) x (Average Number of days that should go by without incident) ] minus [(Percent chance of having an empty hex) x (the number you just figured out DN)]
If you are running a Type A (traveling through) PCs-mostly-riding (D=20) 1-incident-per-day thing (N=1) with high-randomness (P=50% or .50) then you would go for 10 mile hexes and remember to add a 50% chance of meeting nothing to your tables.
If you are running a Type B (searching) (D=3) 1-incident every 5 days thing (N=5) with low randomness (P=20%) then you would go for 10 mile hexes and add a 20% chance of finding nothing to your tables.
See big DIY D&D brains kibitzing on this topic here.