I’m a big fan of wilderness sandbox campaigns, but never been really enthusiastic about the hexcrawling approach, in the sense of “go from hex to hex until you find something”. A 6-mile hex is something like 80 km². Even a large castle might not be noticed while simply moving through such an area, and if the area is forest or mountains, you would have to run straight into it. Spending some amount of time to search a hex to see if you discover something also doesn’t seem convincing to me. If you’re a treasure hunter, you wouldn’t just pick a random spot in the wilderness and start searching it with a fine comb. That takes way too long to find anything of interest. What I believe adventurers would do is trying to make their way to sites that they already know about and that look promising for holding treasure.
Under this approach to adventuring, the players first need to have clues where to look for treasure and adventure. So here’s a couple of ways that PCs can learn of new sites to add to their own map.
Highly Visible: Castles and watchtowers are commonly build on high points where they can overlook a lot of the surrounding areas. Sites like that could be spotted by simply being in the same hex they are in. Or in particularly clear terrain, even by being in a hex next to it. Though if the site is hidden among trees or mountains, it would remain hidden even party is moving through the same hex.
Sites on Roads and Rivers: If a site is directly on an old road or a river that the party is using for navigation, the players discover it automatically when they pass that spot. In some cases, it might even make sense to road signs or something similar point the players that something worth investigating lies down a side path from the road the party is currently traveling on.
Found Maps: Players can find maps among the treasures they pick up which show some sites that are known to them, and some sites that are not. This allows them to go search for and discover the new locations by following the clues on the map. They could also buy maps from certain individuals, or be given a map as a reward from grateful NPCs.
Rumors and Quests: Locals simply tell the party about sites they know but are not on most maps. This also provides the players with some vague idea of what they might have to deal with when they get there.
Following Tracks: After a random encounter, if the players try to follow fleeing enemies or follow their trail to where defeated enemies came from, the tracks can lead them to a nearby site where the creatures have their lair. If no matching site is anywhere nearby on the GM’s map, a quick lair can be put together with a small cave or campsite plan and rolling up a lair encounter by the wilderness encounter rules.
By using all five of these methods to give players hints where they can find new sites they didn’t yet know about, it should be quite easy to make it all feel quite natural and a consequence of the players’ actions, rather than the GM deciding the party needs a new site to be send to. It’s not a big red glowing sign telling the players “the next prepared adventure is here”.