Anton P. Nym said:
Hire Professional writers. Early. And listen to them. And don't screw with the script too much after they're done.
-- Steve
This is almost all that needs to be said, really. Because if game developers would actually listen to this, they wouldn't need to worry about it. It'd work anyway. I've never heard anyone complain about the cutscenes in Starcraft, or in Deus ex. Those are good stories. Well-written. Although I have heard people complain about the cutscenes in Bloodlines, that's only because they are unskipable and they've seen them before. Never the first time.
If you ignore that fact (which you shouldn't since you won't have a good game in that case), there are a few things that can help. Combinations is a very important thing. Don't tell all of your story through one media, like Morrowind, for instance. In Morrowind everything is text. All story is told by text. That breaks the flow of a game somewhat. If you instead tell the story through dialogue, through cutscenes, through books or equivalents and through visuals, like the scribblings on the walls in Portal, then it becomes more interesting. Morrowind got away with it, of course, since it has good writing, a good story (and any other game would to, unless of course the only media was audio and people murmured a lot).
A game needs variety, and a story needs to be worked into the gameplay. It needs to be a part of the game from the start. The usual thing nowadays seem to be to make a full game, and to make the modelling and scripting team write a story for it and stick it on there with duct tape. You do that, and you get the abominations you have today that even the gamers of today complain about, and when it goes that far, it's really bad.