As detailed as a dungeon, ideally...I hex map my wilderness with Arr-Kelaan Software's Hexmapper, 4 miles to a hex, and number the hexes which have detail. (In fact, to support the numbering I made a tileset with a blank whitespace at the bottom of each hex graphic for four digit numbers, but it got wiped in a hard drive crash.

Will have to re-make it sometime).
Some ideas for if you go the hex mapping route: To keep PCs on their feet I suggest occasionally varying the ratio of interest features per hex from something other than 1:1, otherwise they'll only expect something once every few sets of four miles...and also to offer a smallish percentage change that they don't stumble across some hex's interesting feature (so they might discover it on the way back). It's also possible to describe the "patrol areas" of various types of wandering monster with hex mapped wilderness. You might note exactly which hexes in which griffons hunt (and the hex their eyrie is in), and therefore might appear as wandering monsters, for instance. It's also possible to set up areas that call specifically upon ranger and druid abilities, making these classes relevant just as you might add rogue specialty encounters to a campaign. And there's nothing more artificial about this than setting up a purely combat encounter for the fighters, IMO.
I think that a huge opportunity is regularly missed with D&D wilderness, simply because traditional D&D game design doesn't emphasise it. D&D can become fascinating when it involves exploration, and offering the opportunity for exploration is what the wilderness does best....stumbling across ruins, lairs, mini-adventures (e.g. farmer's scarecrow comes to life because of a redcap's prank) and magical terrain features. Once hex mapping gets the detailing discrete areas problem out of the way, there is one big "gotcha" which seperates dungeons from wilderness though, the problem of status quo encounters which the DMG touches upon:
Apart from mountains of the impassable variety, wildernesses tend not to have ways to channel the party into areas that are appropriate for their level.
The nearest theoretical solution I've thought of to meet this problem is to keep the lairs, mini-dungeons, encounters and mini-adventures appropriate to the level of the party, and upgrade them behind the scenes as the party gains levels (within limits - obviously, an occupied troll lair can't contain less than one troll, and the kobold caves can only be upgraded in EL so far before they break the verisimilitude reputation of kobolds not being huge challenges). So if the PC set off to raid Trollden Hill at first level, they might meet a single old and toothless troll with only a handful of treasure...but if they do so at 12th level, there might be a whole clan there, complete with barbarian levels, traps, and a giant two-headed troll leader.
I think wilderness encounters can offer a lot in the way of conveying a world's atmosphere - as an example, Fighting Fantasy's Sorcery! book, The Shamutanti Hills really brings home the exotic and dangerous nature of the Old World. Likewise, stumbling across an abandoned village with many sets of tracks leading elsewhere, or a wizard's celestial observatory (maybe he or she will show the PCs the heavens, and incidentally a falling star which seems to have landed a few miles over there), or a farmstead with an overly hospitable family who invites the PCs in (and subsequently gives them a sever case of the creeps for various reasons) can add a lot of depth to a campaign that can't be done in a dungeon, or through shovelling broad setting detail at the players.
Anyway, it's also interesting that this thread has generated so little interest. Is the wilderness really that irrelevant to D&D DMs?