The first rule of writing a sandbox campaign, I am told, is not to write anything you can't immediately use. This was the rule I threw out entirely. You know those awesome game masters who can make stuff up on the fly as if it had always been there? Yeah, I'm not that guy. I'm the guy who organizes his gaming books by usage before a session to optimize book pulls. I'm the accountant of game creativity. I'm the guy you want running the game store, not writing the games. So I may have, you know, over prepared. I do find my players appreciate this though.
The desire to write a sandbox game came from a few insights. First, I was utterly tired of running other peoples adventures, even the exceptionally good adventure paths from Paizo. It stopped feeling like my game, despite there being a fascinating level of creativity in those products. The best game I've ever played in is the Serpent's Skull game I'm in right now. Absolutely amazing, but not as satisfying as making up my own stuff.
Second, I have been running my home brew urban campaign for a decade and I needed wilderness. I needed trees, and animals, and overland travel. Rule number one for my players: You can't stay in town.
Third, adventures felt too formulaic. They all had the same variables, the same nods to various character classes, and the same conceits, notably power levels and wealth inputs and outputs. You could tweak the curve, something D20 had down to a (dismal) science, but there wasn't much left that hadn't been done. The sandbox promised an organic experience with "safe mode" clearly in the off position. It was dangerous, and that's what I needed. Screw Encounter Levels.
The inspiration for the "campaign" style came from Celtic mythology. The Irish town of Tara, the historical record showed, was ritually humiliated every year by a monster that would march in every holiday, put the defenders to sleep and burn their town down. What a great story! How could you not inflict that on a group of players? On such and such a day, we're coming over and shoving your face in the dirt. Whatdya gonna do about it? This happened every year for as long as anyone could remember, but not this year. Now go.
The detailed sandbox format was inspired by Robert Conley and his blog Bat in the Attic, a guide to sandbox games. Where I went a bit off the rails was in detailing every hex and town as if I were planning to use it tomorrow. I couldn't deal with the minimalist style descriptions you find in books like Points of Light.
I wasn't happy knowing the name of the town and its leader, I wanted to know what kind of problems they needed solving, the shops in town and where the stone from their walls was quarried. Where is that quarry and what's happening with it now? I wanted maps and stat blocks and it's not like there aren't a ton of resources out there for that. There's no need to ever create a dungeon map again, really. The fun thing was you could just keep asking questions and that led to more content, which hopefully held everything in context and was (and this is the hard part) fun. The end result was over 400 pages.
Where this turned from a detailed island the size of Ireland (originally planned to be the Isle of Man) and into more familiar adventure territory was in the timeline of major NPCs. Eight different factions trudged along with their good and evil plans (mostly evil). The characters could help, interfere, or just go fight dragons, if that's what they're into. That's not entirely sandboxy, but a more modern adaptation.
The party could abandon the hunted town of Tara or they could liberate it from its annual humiliation. Because it was a sandbox, anything was possible, so they could lead armies, acquire lost cyclops artifact to boost their power against the forces of evil, or ignore it all and get lost in the vastness of the ancient forests. With 400 pages, it's possible to come back to it a couple times or even have multiple groups playing at once and interacting.
My overland design strategy was to have broken up defined geographical region, like valleys and forests, with two or more factions of good and evil vying for control, and having a mini adventure that could tip the balance of power. I wanted to avoid mega dungeons and create adventures that could be accomplished in one to two sessions. The worst thing in the world is being excited about the sandbox and knowing you'll be spending the next two months in the Dread Necromancers Dungeon of Doom module. There were no off the shelf adventures dropped in. Mini adventures also allows for more casual play, with drop in players, something that has been explored a lot in the sandbox community.
As I began writing, a lot, familiar themes kept popping up. This is because there are only "x" number of wilderness monsters in the rulebooks of "x" power level, so everything possible has more or less already been done. That's where Tome of Horrors really helped out. ToH has a ridiculous amount of animals and plant encounters that helped bring the outdoors alive. A lot of source material arose when they were writing Wilderlands of High Fantasy, the ultimate D20 sandbox set.
Other books that were crucial to the design work included the Paizo Game Mastery Guide, which allows for "statting out" towns to bring them to life and establish their resources. Someone needs to create a book of settlements. The Tome of Adventure Design was a handy brainstorming book for coming up with various plots and schemes. Inspiration came from Hex Crawl Classics from Frog God Games and the D20 version of Wilderlands of High Fantasy. The aforementioned Points of Light I and II were good for a few seeds (written by Conley and others). Every monster book was crucial, Bestiary 1-3, ToH and even the Monster Manual for 3.5 for those proprietary beasts.
As for electronic products, HeroLab allowed me to take Paizo NPCs and tweak them and add templates to existing monsters. The Pathfinder System Reference Document was a permanent tab on my browser.
This encounter calculator helped with random monster tables. It should be noted that "random monster" could be an event, or is otherwise a "monster" doing an activity in which only one may be getting ready to clean your clock. Every region had their own random encounter chart related to what was actually there.
Settlement Creator helped create villages and towns with GameMastery Guide stats. I did not use a mapping program for my maps and did them all by hand. It just worked better that way for me, although I played with HexMapper for a while.
Anyway, I could clearly go on and on about this, but I'm happy to answer questions or take your advice if you wish. There's also our campaign blog and a secret design blog that was more about coming up with the concept. Facebook is where we post information and other campaign documents, in our private group.
One premise of the game is there is no player map. The continent sized island is almost completely unknown and undiscovered. It's so important to the concept of the game that I'm reluctant to post it here. The photo above is how we started.