I was thinking about how stories function in video games, and I've decided that, while they can be similar to other stories (books, film, etc) the interactivity component really does make a huge difference. Some games still try to include a plot, through devices such as cut scenes, but others either don't include a plot or allow the player to create their own plot through the interactive play. Thus, they really don't tell a story in the same way other other, un-interactive mediums.
However, in my experience, it isn't solely the game play that makes me want to play video games. I think, then, that a more important aspect of the game is the premise. The premise is connected to the story because it does establish a narrative world for the characters to function inside, but it is not reliant on a plot to guide it.