So you have this great story. It has interesting characters, clever twists, and asks deep and profound questions that make the person who finally receives the story really think. Then, random game pundits in the massive chunk of oddness that is the realm of cyberspace completely forbid the idea of offloading your story to a bunch of cutscenes. "After all, this is an interactive medium," we say, "If we wanted to watch a movie, we would. We are here to play." And no, we-ahem-they don't like the idea of you making the player sit through a bunch of audio logs or pause to read giant chunks of text either.
"Okay, fine!" you say, throwing your hands up as part of your sarcastic concession. "How do I get this amazing story into the game? How can I narrate it? How can I get all of this exposition out without making the player sit through cutscenes or read walls of text?" First, I congratulate you for being truly unique in that you are willing to write a good story for your game, and then be willing to try to find the best way to express it. Second, I would like to answer your question by writing about it in the time when I'm not busy doing school, producing music, creating videogames, experimenting with electronics, or saving the world from trans-dimensional jelly toads.
The first thing to understand is what exactly you are trying to communicate. A game is like a music track is like a movie is like a book. I want to use the music track analogy since it's the only one I actually have personal experience with. When writing a music track, I may want to tell a story, I may want to teach a lesson, I may want to express my feelings, I may want to create something audibly appealing, or I may want to do a number of these things. As the artist, it is my job to find a way to do them given the limits and tools of my medium. The same goes for a game.
One of the best ways to learn is by example. If you have a simple message like "Nuclear war is dark, grim, and futile," then there is a bigger pool of examples to draw from than if you have a very complex message built into a full sized story. If you have a simple message and story, than Missile Command is an excellent example of elegant game design used to express it. In fact, there is an Extra Credits episode detailing why. But I am assuming that you have something much more complex than that. For that I would turn your example observing eye to games that feature conversation mechanics like Mass Effect and Deus Ex: Human Revolution.
There are of course countless other games newer and older that tell a story as well as these games. There are also just as many games with interesting conversation mechanics, but whatever. The example still stands out because the designers of these games understood that their main goal was to tell their story, and then built sets of gameplay systems that would help them to do so. You don't have to have choice and dialogue options. You do need to understand that the game mechanics are there to serve the story and should therefore be built around it.
But enough with the abstract general ideas. Let's talk hard, fast examples of methods. Possibly one of the most obvious(and most used, often incorrectly) methods of storytelling without breaking game flow is through comm chatter. This works especially well in exploration and puzzle games, as the player doesn't have to be dedicating 100% of their attention to staying alive. They can slow down and pay attention to some other character blather on and unfold the story. Just make sure you don't annoy the player by interrupting them at a bad time with an annoying voice actor.
Comm chatter is probably the least effective use of the tools available to you as a game designer. You should really be taking advantage of the interactivity of the game, and that is where scripting can shine. Watching a touching cutscene where a main character dies, hearing them die over the radio, these things can work but they don't have nearly as profound an effect on the player as watching(and possibly trying to intervene with) their death during gameplay. This technique also obviously has the possible misuse of being used in the same way as a cutscene. Be creative and setup your scripted events so that the player feels like a legitimate part of what is going on in the story.
I've obviously been stalling talking about in-game dialogue. The reason for this is that unless you really hit the nail on the head it can create more problems than it solves. Using this technique along with scripting cam make a game feel more like an interactive movie, which is NOT what you want. I think the key is to have dialogue systems that are fun and interesting to use, allow the player some choice, and flow smoothly together with any other mechanics(if any) that your game has. Mass Effect is an example of a game with good writing and story, but some flawed dialogue mechanics that ended up detracting from it sometimes, and the flow wasn't always perfect. Deus Ex: Human Revolution still stands up as my favorite implementation of in-game dialogue. It flows well, allows player choice, makes you feel like you're there in the conversation, and does a really good job of telling a story and revealing characters. I've actually written an entire article about that if you want a bit more depth on that particular example.
The important thing to realize is that these techniques are merely examples. While I think some of them are here to stay(at least for awhile,) they are by no means the end-all-be-all of storytelling in videogames. The point is to get your mind going and help you understand what makes a method of storytelling in a game good. I will reiterate over the fact that as a designer a part of what you do should be to come up with creative and artistic ways of telling your story or expressing yourself through gameplay mechanics. Videogames are not like music, movies or writing in that there are relatively few conventions that are established as good methods of expression. In order to grow as a medium videogames need people to experiment with different ways to tell stories, because there honestly aren't that many established good ones out there yet relative to other artistic mediums that have been around for centuries.