The story....

I don't think the basics of storytelling are that different in games that you can't look at a movie or a short story and ask the same questions... your protagonist simply has to have a motive (he digs the princess, he digs the puppies) and wants to save them (so often you have to save someone/the world!) In other games it's self preservation, or simply your job as a soldier and you're told to do it.

So I think video game stories are pretty simple to look at in that aspect, and it's easy to compare with other forms of story telling. The part where video game stories usually get fucked are in what follows the instigating moment, where the hero leanrns that in order to save the world he has to collect the million pieces of a crystal. This is used in games, because that extends the gametime significantly, but is terrible storytelling. When have you seen a good movie that employed the searchathon? You haven't, because it's boring!

But video games, as they are, are mostly reliant on this type of story. Even in games where it's not so obvious, you play through a certain area, a scripted event occurs, you play through the next area, another event occurs, etc etc. It's like a movie with interactivity during the boring parts.

So what you really need for a story is something at stake for your character, something that drives him, something that he's willing to risk himself for (even if it is his own life). Take that, and create dilemmas where your protagonist is forced to take action, and even if a player's actions have absolutely no effect on the story, TRICK the player into thinking they do. Think about what you can do in a story to make it more complex, more intriguing or more personal for the protagonist. The easiest way to do this is to have the bad guy kill the protagonist's father, but you might want to consider more subtle ways that a character could make it personal. (To do this, you will need a well fleshed out character with flaws and weaknesses, and not a silent, completely virtuous character (on a side note, has anyone ever made a game where the main character is actually mute? Like his toungue was cut off or something?)). For instance, Jake Gittes in the movie Chinatown wants to get to the bottom of the case because it's embarassing for him, as a detective, to have one pulled over him. (It might get deeper than this, but that's how it starts.)

I lost my point along the way, but I never meant to answer your question... these are just some things to think about. There's no set way to think of a story, especially because I don't think game developers in general have really crafted video games into a new form of story telling yet.