Whether you love or hate sandbox games, this 5 page article at  Gamasutra   presents some interesting ideas on how developers can enhance the interaction of players with story. It's called Stories from the Sandbox. 

Introduction:

 [In this in-depth design article, veteran game designer Sorens examines the 'sandbox game' genre, advocating - with plenty of practical examples - that "designers can and should do more to exploit... player-generated stories".]

The Sandbox Conundrum

What makes the stories in sandbox games special is that unlike the stories found in other types of games, these are not told primarily by the game's developer. Instead, they are created and directed largely by the player's decisions.

The large number of decision points and wide range of possible outcomes in a sandbox game, usually augmented with randomization by various game systems, make the variation in experiences from game to game and from player to player -- one of the key selling points of sandbox games -- both highly personalized and effectively limitless.

Naturally, the developer must provide some amount of structure, as well as the tools the player uses to shape the story. There must be boundaries, goals, and games system that provide decision points. However, the degree to which the player personalizes the course of the game -- and therefore, the story -- is, by the nature of a sandbox game, immense...

On some design ideas:  

...Use goals to provide dramatic structure

Of particular value in the discussion of story formation is the application of goals to the formation of dramatic structure. If designed with this structure in mind, goals can form the pillars of a sandbox game's dynamically generated stories: incitement, rising action, climax, falling action, and denouement.

I will use the game Slaves to Armok II: Dwarf Fortress to illustrate how a game objective can provide or highlight the skeleton for a story and allow the gameplay to flesh it out. When the player is preparing to launch an expedition to build a new fortress, the game could give the player the stated objective: "Survive the first winter."

The dwarven expedition arrives at the fortress site with nothing but the provisions, equipment, and tools in their cart. How the player accumulates the food necessary to survive the winter can be accomplished through many different means... Along the way, many setbacks can occur...

These game events can provide the rising action and even the climax for the story of the fortress' first year. The climax could be a goblin invasion that kills off the only skilled fisher-dwarves in the fortress, leaving it too short-handed to accumulate the necessary food before the river freezes over. It could be the completion of a complex irrigation system that allows the dwarves to sow a large farm and reap a bountiful harvest before winter sets in. It could even be something as odd as a dwarf going mad and slaughtering his compatriots.

The falling action and denouement would finish the story of the first year at the fortress...

"Collect (or kill) 100 foozles," with no apparent purpose or connection to anything else in the game, does not lend itself particularly well to a story. However, "Collect 100 Philistine foreskins in order to marry the King's daughter" could be more intriguing...

On characters: 

...Give characters human qualities

It is easier to see the game's events as a story when the player has emotional ties to those events. There are many methods of increasing this feeling of attachment...

Robotic and soulless characters disconnect us emotionally from the game and cause us to focus on abstract constructs instead. For example, an encounter with a typical MMO enemy, the epitome of soulless and robotic video game characters, does not even register on the emotional scale, and our thoughts during this encounter focus solely on the gameplay-related characteristics of this enemy -- hit point and experience levels, ability timers, etc. -- instead of caring what part this character plays in a story.

I've snipped just a few parts of this article, so head over to the link above for the complete story.