In one of these threads with the word sandbox in it, Ariosto or somebody shaped like him mentioned that sandboxes are/tend to be location-based.
Let's roll with that as an extreme example for a minute.
Make a village. Assume a series of imaginary concentric circles around the region, where the farther out you go, the higher level the encounters (either pre-generated or just by random encounter table/level).
Also assume a scattering of dungeons, where the deeper you go, the more dangerous it gets.
The village has a mix of services, to meet the needs of a low level party. Farther away, is bigger towns, with "higher" level services.
The assumption is, to fight bigger stuff, travel farther, go deeper.
This is sort of the points of light model, and in reality how I suspect many D&D campaigns start.
Assuming the NPCs are boring, and the PCs like killing things and taking their stuff, you have a location-based sandbox. The players are free to go anywhere, and try to kill what they encounter.
What would a DM do to spice this campaign up? Probably make the NPCs more interesting, with job offers, betrayals, secrets, and opportunities to advance socially, etc. Once you start the "people" moving, then things are happening within the world beyond just the PCs actions. Suddenly, we're not just location-based, we're something else.
This doesn't break being a sandbox or not. But running a pure location-based sandbox is pretty cut and dry. Once you start modelling more complexly, the game style transforms.
Here's some sandbox console games I've played or seen:
Grand Theft Auto
Driver
Elder Scrolls IV Oblivion
Spiderman 2 (not the movie based one)
If you take out the "missions" or "plot" stuff, you can basically start the game, and go anywhere. The NPCs are all boring. You can kill them, or rescue them from random encounters. You can run from the cops. This is kinda like the location-based I'm talking about (I'm not talking about encounter difficulty, put that asside for the moment).
To make the game environment richer, you make the NPCs seem just as real as the PCs. You make them move about and make some of their actions intersect the PCs.
What I'm talking about describes what I think is the approximate evolution of D&D. The exact rate of change matters little. I suspect after the first game, Gary got some ideas and the next session was different.
As you start focussing on NPCs and their interactions, it becomes apparent that quests that are like stories becomes apparent. There aren't any stories about killing monsters and taking their stuff, though stories have that stuff in them. That causes a shift in how adventures are crafted and documented.
The danger of course, is that there are some pretty crappily designed adventures that look like railroads. Namely because documenting locations can be a fairly finite process. Documenting the possibilities and results of PC interactions with NPC goals is far more complex and tedious. So short-cuts get taken.
What has this got to do with sandboxes?
I suspect a sandbox DM should document locations and NPCs and their goals, but nothing else. He then runs off the cuff with regards to how they proceed (when it matters to the PCs) and moves the pieces around as needed.
Coincidentally, I don't tend to write time-lines in my adventures. I document the locations I think I'll need, and the NPCs involved with the 'story' and a rough outline of their goal and how it'll probably intersect with the PCs.
After that, I move stuff around as needed to keep the game going.