I start with two documents: one for the players, and one for myself. The initial "player guide" contains:
A page-long introduction to the campaign setting. This is a teaser, so I keep it brief. Character creation guidelines. House rules.
My "GM guide" is a typically a stream of consciousness mess that parallels the "players guide", but focuses on information I need to know. Most of the initial information I give to players is incomplete or wrong, so this is where I detail the missing bits, misconceptions, plots, etc.
I also create a Proper Nouns spreadsheet with people/places/things and a one-line blurb describing each. This serves as a Cliff's Notes to the players, and I helps me avoid creating NPCs with confusingly similar names.
I update these documents as the campaign proceeds. The "player guide" usually hyperlinks off to additional documents with greater details.
WHO: Who are the major players? (Individuals, Organizations, Nations)
WHAT: What's special about my world? (Novel premises, weird rules, etc.)
WHERE: Make a basic atlas! Players love maps, even crappy ones.
WHY: Why is my world different? (Explain the WHAT)
WHEN: What are some defining events? (How the World Came to Be, wars, etc.)
Be wary of writing universes from scratch. The more you diverge from the "standard" campaign rules, the fewer pregenerated materials you can use/adapt. Where you do choose to diverge (e.g., custom magic rules) make it clear and compelling.
Fortunately, Hero System makes this easier. Try changing the spell system in D&D....
Steal liberally from other sources: books, TV, movies, other games, your players.
Only be as specific as you need to be. Locations far away or events far in the future (e.g., hidden plots) only need to be sketched out. This saves you from unnecessary effort detailing stuff the players may never encounter. It also makes it easier to change your mind as the distant locales/events come into focus.
Stuff of immediate concern to the PCs should be fleshed out, at least to yourself. Be comfortable enough with your setting to answer questions from PCs on the fly.
Doug
"Wait, when you said [our contact] Anne killed them, did you mean Anise [the villain]?"