There are different thoughts of what constitutes a "sandbox" in an RPG sense, but it's basic definition comes down to "player choice".
For some campaigns, the players choose the direction and the GM has to build things quickly around the party's choices. This, in my opinion, is the hardest type of sandbox to run successfully. You need a group of players that can thrive without outside direction, a setting with enough history to take on a life of it's own (and players well versed in the setting, as they are manufacturing the plots for the most part) and a GM that works well improvising on the run (and does an even better job of documenting all of his improvisations, else discrepancies will come back to haunt him. I'm good at the improv part, horrible at the documentation ;)
My sandboxes are usually sandboxes with built in choices. Enough options to give the players validation that their choice has value in the direction the campaign takes, but not so many that it seems their options are overwhelming. When your options are overwhelming, your choice seems to have little value. For the campaign to be successful, the players choices must have value and meaning, for both the PCs and the setting.
That isn't to say the PCs can't choose a choice that isn't one of the ones presented via rumor / hook / history. Players often find their own trouble, and a sandbox style campaign is built to handle such with minimal issues. It's hard to derail a plot train when there isn't a train or tracks to be derailed. Still, the GM must be comfortable improvising, even if its only roadblocks to slow the players down so you can prepare for the new twist in time for next session.
I also keep my initial sandbox relatively small. Large enough to offer the PCs valid choices, but small enough that they can feel comfortable with their surroundings, and knowledgable of the events that are happening around them. When it comes time for the players to explore new surroundings, I just pull back the focus, expanding the sandbox.
In a sandbox, characters can influence the setting, but the setting continues without them too. Events transpire in the background. The PCs are just one component of a larger story (in Adventure Paths, it often seems that the world revolves around the PCs).
So, thats my basic sandbox setup. When I next post about sandboxes, I'll be talking about placing the nasties.