I keep it real.
1. Interesting story with a fixed framework. The DM and players coordinate around being a part of a campaign theme. Current campaign is: "you are empowered to raise a barony." Perhaps you raise a kingdom, or mageocracy, perhaps you rise up against your benefactors, or recruit the bandit element you worked so hard to clear out. The DM doesn't craft the situation. Rather, everyone does, and everyone works towards a common story. The DM maintains a "behind the scenes" framework of events that move forward, whether PCs are reacting to them or not, so the story isn't completely up to PC action. Don't take the One Ring to Mount Doom? Sure, the bad guys move forward and begin conquering region by region. Pretty soon, it'll be sad little hobbits in chains.
2. Randomness rocks if impacted by character decision making. This follows the lack of a pre-scripted story. In the current campaign (Kingmaker, from Paizo), random kingdom events each turn along with preset political flavor create a fluid part of the campaign to complement #1's fixed framework. However, it's not the random event that moves the storylines that unfold. It's player reaction to them. Give the widow of the man who died because you didn't catch the marauding werewolf in time because you were gallivanting out in the countryside looking for treasure a pension? She won't hate your rulership, join the hag cult and later become part of a plot to switch babies in their cribs with changelings, nor assassinate your soldiers.
3. Let the dice fall as they may, but "role-play" supersedes "roll-play." In original D&D, puzzle solving and some metagaming occurred as gamers tried to solve situations. No character had skills. In tournaments, you were rewarded for clever play. At the table, good DMs would reward bold, intuitive play rather than stifle it. Your gnome thief wants to leap off a 20' overhang onto the back of a marauding blue dragon, and the player makes the case this should (in AD&D rules) count as a backstab? Was it bold? Was it unexpected? Is it plausible? Then let's do it! Nowadays, too much reliance on "roll-play" can (can being the key word) stifle this creativity as we turn to page 1xx, reference Athletics, figure a DC, and reward that creativity with a 50/50 die roll or by saying "that's not RAW, you can't." So, in summary, I aim for a "yes you can" style of play when it comes to creative solutions and worry less about RAW when it comes to skill and ability score usage.
4. Get everyone involved in describing the world. The DM shouldn't always be the one describing the world. Pretty much anytime a natural 20 is rolled, I ask for the player to describe what just happened. If the player fumbles a bit, I leap in to assist rather than put them on the spot. After awhile, players might look forward to saying "this is how it happened" or "this is how my character felt when she struck down the Prince of Darkness."