In my own experience "setting depth" best comes organically.
Take this idea....run with it.
For me, depth is how many questions a character can ask before we hit "suspension of disbelief" critical mass.
If you have viable and sensible answers for the questions the characters ask, your setting is as deep as it can ever really be. Any more depth isn't really depth, it's just detail.
You can answer these questions before the session: think of what questions the PC's are likely to ask (where does magic come from?) and think of an answer to have ready (fairies).
You an answer these questions durring the session: PC makes a wizard, you tell him "Magic comes from fairies. Your familiar is linked to the world of the fey, and thus they are how you access magic. If your familiar dies, you cannot cast spells until you attain a new one."
You can answer these questions after the session: PC makes a wizard, you tell him "You don't know exactly where your power comes from, you just know how it works. If you have more curiosity, you may want to ask around." In between this week and next, you work out an explanation.
Some reactions...
(1) Mysteries that the player characters can potentially solve with the investment of time and effort. It is important that the players actually hear about these mysteries before the adventure they can be resolved in. Depth is based, in part, on the way ideas resonate over time. You do a disservice to your campaign if you do not allow some ideas a fallow period between when they are first mentioned, and when they become important.
I love making these organic. E.G.: All I know about the Dragon Shaman villain for this adventure is that he's hoarding wyrmlings for Dark Purposes. Until the PC's are able to discover more, I don't need to seed more...their question and my question are the same thing. When they ask the great Dragon Sage, perhaps he knows a bit of it, let's say he believes it's linked up to the planetary conjunction...
So you leave a trail of breadcrumbs, always working just one step ahead of the PC's, until you get tired of it. This way, there's always more in the adventure than the PC's can explore, and these avenues work from big things to small: (Dark Purposes -> Planetary Conjuctions -> Opening of the Far Realm -> An eventual encounter with pseudonatural dragons, which has been presaged from this first encounter with a Dragon Shaman and his wyrmling-hoard).
My closest analogy is a puzzle: I don't know what pieces this Dragon Shaman fits into until I find them. Neither do the players. But I'll find an idea knocking around in my head, or even an idea a player gives me, and find it fits nicely.
(2) Precise description. It's better to say the type of stone than just the word "stone" and takes only a little more effort. A "stone wall" supplies less information than an "obsidian wall". A stand of pines is preferable to a stand of trees.
This kind of thing is great for adding on-the-fly worldbuilding for me. If I mention in an off-hand detail that the walls are obsidian, I know that there was/is a lot of geological activity in the area: volcanoes, rifts in the earth, etc. Thus, I now have a location for the future: the Great Rift of Dolmurh, where Azer enslaved by the Red Dragons build great works out of obsidian.
I didn't know it when they started along it's length, but by the time they camp for the night, I'll have jotted down the notes and seeded the future.
(3) Pick details that count, but don't make every detail significant. It's important to mention the monkey-lizards in the cave complex if they provide potential food (including for monsters), if they provide a bit of unkown (the PCs don't know if they should fight or not), if they can be animal companions, or if they help to make the adventure setting unique. It isn't helpful to detail every rock on the cavern floor. Mention that a stalagmite resembles a hunched over dwarf without worrying that it isn't important; not knowing what is significant can be a major ingredient of sense of wonder.
This flows back into the previous point for me. Details are easy enough to generate that I can pepper my descriptions with them without worrying about if they're important until/if the PC's pick up on one. If a PC determines that the "purple deepmoss" on the walls is important, then it can feed into the Planetary Conjuction theory or not. Depends on if I've thought of a better idea.
(4) Choose details that make sense. Keep a list of names that fits your cultural area, and a list of small details (dungeon dressing, etc.) at hand at all times. Whenever the PCs decide to question a peasant or an orc, you can easily tell them his name. Suddenly, it's not easy for the PCs to pick out the hidden Important NPC because he has a name.
If I've got my laptop, I'll use a random name generator (some of the best can choose from amongst different real-world and fantastic cultures). If caught unprepared, I'll just pull something out. "Let's see, the PC's are in elven lands, elves speak with a lot of breathy-sounding names, let's call this elven guard Allhueyu."
(5) Include encounters with animals. Include encounters with animals that have no combat in them (even if in passing). Mention the squirrels in the trees, or the deer seen in a sun-dappled clearing. Not only will it give the Druid something to do, but when you decide to throw in a wolf-in-sheep's-clothing or an NPC's familiar spy, it won't be obvious.
I wouldn't call those encounters in the "13.3 encounters" sense, but the point on diversity and establishing the ordinary is key. Mention birds singing so that the lack of them is key. Mention what the rocks "ordinarily" look like, so that when you mention something else, it sets off keys in the PC's head.
Mentioning once or twice establishes a good "average" and lets you play all sorts of tricks (usually, I do secret Perception checks when I think that a spy or the like is a likelihood, thus making sure that observant PC's don't have to rely on players mentioning that they watch the squirrels suspiciously).
(6) Give your players compelling reasons to like the common people in your world. Let them give the PCs free room and board, or offer to mend things for free. Let them be honest. Then, when the NPCs ask the PCs for help, the players might actually care instead of saying "OK, guys, I guess this is tonight's hook...."
Realistic NPC's are a good component of depth. NPC's usually have family (and usually a lot of family, in the pseudo-medieval feel), community, history, nervous twitches, common appearances (all the farmers of the Dales wear a green sash representing their dedication to the Green Lady, a druid who blesses their fields), etc. Like with the details points, it's important to mention off-handed details, whether or not they become important later (how did that brewmaster get the scar?).
(7) Don't be afraid to allow time to pass in the campaign world. PCs don't have to rocket from 1st to 20th over the course of a year.
I steer away from down time because I dislike PC's "sitting around." It detracts from the action and drive of my campaigns. I'm a fan of active characters and active villains, so I cut down on in-character down time whenever possible.
But my campaign worlds only exist for single campaigns for the most part, so they don't need much in the way of chronology.
(8) Anything the players express interest in is significant. If they want to talk to the local cleric about religion, let them, even if you have to make it up on the fly. If they want to skirt the Dread Forest, let them, even if it means you wasted a dozen encounters.....you can always use them later. If they want to circumnavigate Dino Island on a raft before exploring the interior, let them. Any time that the players express interest, they are investing themselves in your campaign world.
This is especially important in my games because this is the only way I'll think about these things. If the PC's run right to the castle to kill the necromancer king, well, I'll follow them. And if the PC's float about outside of Dino Island, I'll follow them there.
This is part of why I've more or less abandoned pre-preparation for my adventures. I let the players lead my nose, and make up stuff as they ask for it.
(9) Never tell the players when you are winging it....but be damn sure to take notes. Consistency is easier to maintain when you can look at your notes about what was south of the Dread Forest, instead of having to try to remember.
Very key for my style -- the notes ARE my setting bible. My players know I don't really do prep work, but they seem to like it when they tell me what they want rather than me telling them what they want.
(10) Never run a game that you aren't interested in. If your interest is shallow, you can bet that your game will be shallow, too.
True enough. This also applies to DMing in general -- if your heart ain't in it, give the reigns to someone else for a while. And if no one wants to, do something else. D&D is never anything you have to do.
