So you are wondering how to prepare for a game with total player autonomy? There isn't much you can do except get a good set of systems in place that help you improvise. Be fluent with the random tables and monster manuals, wilderness travel rules, dungeon generator, and read a lot of pulp - this will cover most bases. To make things easier, pre-rolling random encounters, (those MM encounters with big numbers and high level NPCs take a while to roll up at the table) as recommended by Bdubs, is a good use of time.
|Terrain (Using DMG Appendix B p173)
This post combines the DMG and FFC to give a way of stocking wilderness consistent with the wilderness generation method laid out by Gary in the DMG, and the lair probabilities + monster distribution laid out by Dave. The general gist is that Dave decided how many lairs actually exist in the wilderness (about 2% of wilderness square miles are lairs) and for each 100 square mile area he would roll a d6. 1-5 meant there were that many lairs in the space, and a 6 meant the hex was empty (of lairs, though it could still have ruins, settlements, etc). He also detailed how much of the monster population is at the lair, and where the rest of them are in what proportions (this gives you scouting parties, war bands, patrols, etc.)
|Habitats, Ruins, & Castles (DMG p173, p182-183)
This can be extrapolated to whatever hex scale you like (see the linked blog post for calculations). I see it more useful on the smaller scales (such as a 5 or 6 mile hex) since that is more likely the scale you would use for finer wilderness exploration/lair hunting. Using just a 30 mile hex works fine but I don't have a good way to manage finding things within it without great abstraction/hand-waving. On the contrary, a much finer scale seems too finicky/localised to be broadly useful except in solitaire-domain cases (DMG p93 "Territory Development"). I opt for a 5 mile since it divides nicely with the standard 30 mile campaign hex as well as the wilderness movement rates (DMG p58 "Outdoor Movement").
The entire process is quite swift - in an hour or two you can have a good chunk of wilderness terrain determined, with the lairs inside it, ruins, inhabitants, etc.
Now, to reconcile it with the DMG encounter tables when the PCs are exploring (obviously you still want that chance for a random dragon or other whacky encounter), I would simply make another encounter table such as:
d12: 1-7 = occupant encounter
8-12 = truly random wilderness encounter (from the tables in the various monster books/DMG)
You could adjust this probability based on how active the occupants are, how big the lairs are, etc. Perhaps even include adjacent hex occupants as an option.
If the players land an occupant encounter, you would then roll % in lair to see if they actually stumbled upon its lair. Otherwise, it's one of the patrols/external parties.
Now, this preparation can really set the stage for inter-monster conflict at mass combat scales - simply refer to their alignment, lair size, and, a good rule of thumb for their radius of influence, is their movement in miles (so a 12" movement = 12 mile radius around the lair). It's possible you could pepper your encounter chart with evidence of conflicts, campsites, etc. (rather than just running into the monster itself).
A final note - Arneson also included rules for managing migrations, population growth, and conflict within the lair (all as a function of TIME), as well as his own wilderness generation method. The First Fantasy Campaign is worth reading, for in many ways it is a missing link, and can provide great utility and insight into how to run a BrOSR D&D campaign.
|Lairs, Ruins, Terrain, and Inhabitants - messy, but useful...