The answer to that is to not give the players a blank sheet of paper with only one circle that says "you are here". With that setup, you really only can wander off into a random direction and wait for the GM to tell you that you found something.
At the very bare minimum, you need a circle that says "you are here" and an X saying "dungeon". But if you really want to give players agency, there should be three Xs that don't just say "dungeon", but rather have an evocative name that suggest something interesting, and the locals in You Are Here should be able to provide some more information about them when askes. And all three should sound meaningfully different. "Haunted Grave Mounds", "Monster-spawning abanoned mine", and "Bandit camp in the Spider Woods" for example.
However, all of this only works if the players have made characters who are looking for places that are crawling with monsters and promising treasures. Which brings up another important differentiation of sandbox campaigns:
"Are the PCs exploring the land or are they trying to accomplish something?"
A sandbox that provides plenty of opportunities to find ancient treasures has to be designed quite differently from a sandbox that provides opportunities to found a new settlement. You can even have a quest based sandbox with the established goal of "Free the land from the rule of the evil sorcerer lord." If it's up to the players to gather allies and weaken the sorcerer's forces, that'd still be very much a sandbox. But it would require a very different kind of setup in regards to what sites and people populate it.