I consider a game's story to be the subset of narrative content authored for that game, which the player interprets to have some coherent meaning. The meaning does not necessarily need to be placed there purposely by the game's creators, it just needs to be perceived by the player through the intuitive pattern-matching we conduct as we go about trying to find meaning in all things. Story is just one of many types of feedback games can employ in response to the player's input. Thinking of story as another form of feedback, I think, is the key to tapping its potential in games -- as well as the key to integrating it into the design process in an appropriate way, while mitigating risk of the story derailing or constraining the design.
Game feedback, in general, provides information, confirmation, and affirmation. Story is no exception; I can draw an analogy between story and user interface design. In God of War III, a big spinning "O" button next to a prone enemy carries a specific, almost Pavlovian connotation: Here lies an enemy that you can savagely murder if you get close to it and press the corresponding button. The UI prompt is a reward, affirming your combat skills; it confirms the availability of a unique set of killing moves; and it informs you of the input required to access those moves. Good interface design in games is contextual and just feels right, in this fashion, because it's closely linked to player input and the affordances of the interface match the aesthetics of the game in general or the input in particular. Think of "You Are Dead", the game-over screen in Resident Evil. It works like a consolation prize, not a punishment. It's a pretty good screen.
Linear noninteractive game narrative tends to be ineffective because it's disconnected from the player's actions. However, there are numerous games with lots of noninteractive cutscenes that are still considered to have outstanding stories in them. These games range from Grim Fandango to Metal Gear Solid to Mass Effect. How is it that these examples break from the popular player-elitist idea that linear story is a bad thing for a game? The answer is that, in addition to having these lengthy story sequences in them, these games do the important small stuff too: inform, confirm, affirm through the story.
In Grim Fandango you can share your balloon animal shaped like Robert Frost with various characters, leading to unexpected comedy. In Metal Gear Solid, a character called Psycho Mantis looks for saved data for Castlevania: Symphony of the Night on your memory card, breaking the fourth wall as he points out your gaming preferences. In Mass Effect, you can shoot one of your party members dead if you don't like the way he's acting. By affirming the player's actions in these types of cases, these games inform the player of a wider-than-expected possibility space of interactions, which the player later confirms (or does not confirm) through additional interactions along the periphery of that space. These are examples of story working at its best. It's supported by a rich linear narrative in all three cases, which cushions these smaller, more-important story moments in deeper meaning. The result is three very different yet rewarding experiences that share in common a story-driven structure, where the player's input is acknowledged via story mechanisms and not just interface prompts as in God of War III. Nor are these games' stories simply playing out without respect for the player's actions, as is the case with many games reviled for their flashy noninteractive stories.
Animal Crossing is another excellent game that uses these types of techniques but does not have story in the traditional sense, because (following my first statement) it has no coherent meaning behind what happens in the story -- except for the thinnest possible premise of "Tom Nook gives you a home loan and eventually you pay him back." The game has the perfect amount of story for something whose underlying meaning concerns the simple pleasures of life. But even though Animal Crossing would never be considered a game story on par with Grim Fandango, or Metal Gear Solid, or Mass Effect, it is just as effective in its application of game-story principles. One of my favorite examples of this is in the game's clothes-making mechanic, where you can "paint" clothing patterns and put them on display in the local clothes store. This type of player expression is very common in games, which routinely let you change your character's hairstyle, paint your car, and so on. However, Animal Crossing takes these types of systems a step further by affirming your efforts, as when you find one of your town's animal residents wearing that shirt you made and complimenting you for your artwork.
Games rarely go to the trouble of confirming, let alone affirming, this type of player expression, as though we're all so confident in our ability to express ourselves that we don't want the world to judge or acknowledge our efforts. But, if you'll forgive another one of my analogies I've been meaning to commit to writing, think for a second about what happens the day after you get a new haircut. Either you're fishing for (or at the very least you're open to) compliments on your new look, or, if by some chance you're someone who knows her hair looks excellent, I figure you at least expect people (even just certain people) to notice the change. Conversely, you'd feel bad if no one noticed or seemed to notice. Doesn't mean you want to be fawned over in the way certain games vomit praise on you for your basest actions, like a mother indulging a spoiled child. You're sharp enough to observe subtle cues, as when someone who never once paid you a second glance does a quick double-take. And what a rush that is. Story in games should serve this end. All it really needs to do is acknowledge the player's input in a way that seems to give meaning to the player's actions, by being personal or specific or both. It also doesn't need to use a lot of words or cutscenes to accomplish this.