For games in which content is written primarily by human beings, creating such flexible narratives is almost certainly impossible given the number of potential choices for the player -- far too many for any author to account for. On the other hand, for games in which content might be generated dynamically with the aid of computer algorithms, current Artificial Intelligence approaches aren't advanced enough to produce engaging narratives.
A less ambitious goal, therefore, is to make games in which players' decisions are limited but significant: limited because the possible choices and outcomes are only a small subset of those that would otherwise be available, and significant because the players' choices make sense to them and have a perceptible effect upon each game's environment. Even so, merging together narrative and gameplay is difficult to accomplish successfully.
Players should be offered meaningful choices
"Is doing X a better choice than doing Y? Why?"
For players to make effective decisions they need more information than games of this type typically provide. A game's narrative should be crafted in such a way that players can, in most cases, make informed decisions. This doesn't mean that optimal choices should be obvious or require no work to ascertain, but that players should be given the chance to foresee, to a reasonable degree, the possible consequences of their actions. Always provide enough information for players to have some idea of what the outcomes of their actions might be.
Players shouldn't be afraid to make decisions
"What if I make the wrong decision? Can I try again or am I stuck with it forever?"Players may fear the possible consequences of their actions, leading to what some people call "analysis paralysis". It may be that players lack sufficient information as to the possible outcomes of their choices, or it may be the game is designed in such a way that players expect the consequences of their actions to follow them for the rest of the game. Players should have enough confidence in the game's design to know their experiences will not be ruined by making the "wrong" choices. Avoid long-term negative consequences and allow players to recover from undesirable outcomes.
Players shouldn't feel like they're missing out
"What would've happened if I'd done Y instead of X? What if the alternate ending was better?"
Having multiple paths for players to follow means players don't get to see all of your story. While this conceivably adds to the game's replay value, there are players who would rather not play through the entire game a second time just to see the parts they missed. Alternate endings are often little more than a gimmick, a testament to the narrow set of choices offered to players. Consider whether paths not chosen really add to the player experience and keep in mind that a narrow set of choices does not truly afford a sense of freedom.
Avoid the illusion of choice
Damned if you do, damned if you don't.
It may be tempting to have a large number of alternatives for players to choose from, but if all the alternatives lead to the same outcome then all you're doing is providing the illusion of choice. As already stated, providing significant choices means that players' choices actually make a difference in the game. Avoid offering choices that don't make any difference.
In light of the fact that players' choices are severely limited compared to real life, avoid shallow, falsely personalized narratives in the style of "Choose Your Own Adventure" stories and instead make your narrative elements integral parts of your games' puzzles -- into parts of the games' mechanics. Just like some games call for the manipulation of objects in solving puzzles, games with narrative puzzles call for the manipulation of dialogue and story elements in pursuit of each puzzle's solution. This avoids the problem of complicated branching while still providing meaningful choices in the context of each game's narrative.