I run many overland hexcrawls and use a standard procedure for doing so. Step 1 is "Determine the weather and any paths." I've already mentioned how I determine the weather, but I don't think I've ever discussed how I determine paths.
My procedure is fairly simple. I find this fast enough to use at the table, and will often have the players execute it directly instead of rolling for them, though they may have to search first. Most of the time, paths save you travel time but aren't required for movement into adjacent hexes. Occasionally, in very difficult terrain, following a path is required to move from hex to hex.
Paths go from the midpoint of one hex to the midpoint of another.
Start at the midpoint of the hex the PCs are in. Roll 1d4-1 and note the directions of the points of the d4's base. The value of the roll is the number of paths exiting the hex.
The points of the d4's base will roughly point to surrounding hexes. If there's ambiguity, feel free to adjust the die 's physical position slightly. Draw paths to the midpoints of the surrounding hexes, starting with the point on the d4's base that has the lowest value and ascending until 1d4-1 paths are drawn.
If the die points in a direction where there's already a path, rotate clockwise to the first hex face without one.
|The result of the d4 roll here is 3 (4-1) so we draw three paths|
|The PCs choose to move along the northwestern path.|
|Here the die result is 1 (2-1) so we draw one pathway.|
|Repeat each time the PCs move.|
|The first option already has a path, so we move clockwise to the next face.|
|...Resulting in this|