First off, there are some hints for history generation about Dwarf Fortress. Someone asked on the Bay12 forums a while back, and a transcript was shared and you can find where the discussion begins by searching for: "our topic today is world generation and history generation".
I don't know exactly how Dwarf Fortress does it, but I'll explain how I'm planning on implementing a very basic first draft in my game. I'm going to use a simple cellular automata. If you look through these Spore prototypes, like cell culture and biome.
These are examples of cellular automations and what they can produce. Essentially I'll create rules for different races. Some examples of rules would be:
- Their hostility towards other races
- Their climate preferences
- Their resource requirements
- Their birth rates and life spans
- Their desires (technology research, commerce, peaceful existence, world domination)
- Their capabilities (structure building, resource gathering, war making, etc.)
- And so on...
So, the most critical input for all this to work is a world to plop these races into. The terrain will determine their preferences and expansion. So once you've generated a world, pick random locations in the world where these races would suitably live and let them loose. Now the interesting stuff starts happening. Now that you have land and races with desires and capabilities, you can start building a history. These races gather resources, then structures are built:
- Towns in high resource, high livability areas.
- Roads connect the larger towns.
- Bridges across rivers.
- Tunnels through mountains.
- Fortresses near the front lines of expansion in response to battles.
Any structure can be raided/conquered by other races. The longer a structure (like a town or fortress) exists in history, the more defensible it is, the harder it is to take over. And the more desirable it is for races that want control. Battles are waged where races meet (at at least one is hostile). Battles are named after landmarks or nearby structures, or if the battle is significant or the landmarks are not named, the landmarks are named after the battle.
Roads, bridges and tunnels are expanded through commerce and resource transport. Each has a maximum throughput that can increase with resource expenditure. Building a stone fortress in the middle of grasslands? Those roads are going to get heavy use transporting the required stone. They'll become larger and get a name.
Natural disasters occur, affecting populations and the course of history. Earthquakes might reduce a town to ruins or collapse a tunnel. A flood might wash out a road or bridge.
It's all a simulation (albeit complex), you're just recording the important events along the way and calling it history.
I also just found a Bay12 forum post for people brainstorming how to make the Dwarf Fortress world generation faster. I haven't read through it, but it may provide some hints if you ever run into issues with your implementation being too slow.