Three traditional ways of modeling stories are strings, beads, and trees. A string is the simplest representation of a reader or player's journey through a story. The player can only take in one sentence of data at a time, and each piece of data has to make sense in the context of the ones that came before and the ones that will come after. These two principles, causality and teleology, which together result in suspense, are the reason the player's mind perceives a string-like unified journey from the beginning of a story to its end. A string is a good metaphor because it doesn't have to go straight, it can curve or zig-zag all over the place, tie itself in knots, form a loop or a spiral, or weave together with other strings. Stories are also like this - the kind of story where the end is predictable from the beginning and nothing surprising happens in the middle to challenge that prediction is boring. Stories that keep the same pace and level of tension throughout also get boring, the human brain responds better to a sinusoidal oscillation or a square wave. This is true of gameplay as well - any game where the player can alternate between two different types of gameplay will take a much longer time to get boring than a game where there is only one uniform type of gameplay. If you're making a game which tells a linear story, this is sufficient. But if you want the story to be interactive, we need more structural ideas.

Once you have a string, you may if you like string beads onto it. A bead is self-contained, modular. It has to fit in the context of the point it appears on the string, but after that it's gone, not to be revisited. So, a bead can represent a cameo appearance by a character who is not going to appear in the story again, or it can represent a self-contained mini-plot where only the outcome is important to the rest of the story, or it can represent the details of a scene of the story which the reader doesn't really need to remember because they aren't going to be relevant later. Beads are a helpful concept for computer-izing stories because a software which can do a limited amount of modeling of the player's past actions (memory) and future actions (goals) will make the best storyteller. Beads help separate what the computer doesn't need to remember or anticipate from what it should remember, anticipate, and communicate to the player about.

For the memory portion of the software's model of the player's story experience, arrays and meters should be sufficient. Arrays are already used to keep track of the player's name, appearance customizations, equipped gear, finished quests, chosen classes and professions, titles, purchased or learned spells and abilities, opened chests, solved puzzles, etc. Meters are already used to keep track of XP and money, possibly other character stats. A few games use meters to keep track of the character's relationship with factions of other individual characters, as well as progress toward goals provided by the game (collect X thingamajigs, discover 100% of the map, kill Y monsters, do something before Z time elapses. For both arrays and meters, my suggestion is merely to do this systematically instead of haphazardly, and then allow NPC dialogue to access this data and modify itself based on this data. NPCs who react to what the player has done within the game so far help create an immersive and satisfying gameplay experience, and building a programming structure to control these reactions in a systematic way allows for greater complexity and consistency.

Anticipation is a bit more complicated. You can try, through both design and playtesting, to try to anticipate every goal the player might want to accomplish within the game, and build recognition of these goals into the game. Or you can try to built a bit of statistical analysis software which observes the players actions within the game and tries to draw conclusions about what the player wants to accomplish. In a limited form, current games may do this as achievements. An example: spend at least 6 hours playing a minigame to be rewarded with a title recognizing you as a fanatic of that minigame. Or: get to the middle of the game without having any characters die and get a reputation as cautious or unkillable. Statistical analysis is more relevant to an MMO context, or a Fable-like sandbox game. Statistical analysis is mainly about what percentage of their time players are spending doing which activity within the game (do they spend a lot of time flirting with NPCs, a lot of time fishing, a lot of time PvPing...), or if they consistently prefer one choice from among several (do they own more items of one color than any other color?) Psyhological profiling within the game is often possible, either by asking the player direct questions or by looking at the player's actions (a player with several areas at less than 100% completely explored and less than 100% treasure chests open is probably not an explorer/treasure hunter/completist).

Oops forgot trees. Trees are a somewhat old-fashioned way of looking at interactive story. Basically a tree is a string which has decision points; at each of these points the player makes a decision, choosing which branch to continue traveling on. A single playthrough of the game corresponds to a linear path from trunk to largest branch, smaller branch, smaller branch, until getting to an ending. There may be one ending per final branch, or some of the branches may be gathered back together so fewer endings need to be created. A tree structure tends to be unsatisfying to both the player and the developer. The player doesn't get very many decision points and may have to play the first part of the game again to experimentally change a later decision; the developer creates a lot of content that someone who only plays through the game once won't see.

A combination of beads and weaving multiple strings together is a more flexible approach. Miniplot beads can partially customize the genre of the game's story to the player by offering the player optional chances to participate in subplots of different subgenres (romance, mystery, crime, horror, military, etc.) The fact that these subplots are self-contained means that the story doesn't have to branch each time the player does or doesn't accept one, and allows the player the flexibility to abandon one in the middle if they decide they don't like it, or leave it half-finished until later when they are in the mood for that kind of content. Weaving multiple strings together allows a complicated tree structure to be simplified into several smaller trees or beaded strings. For example, instead of having one branch where the player chooses to join a military faction and a different branch where the player chooses to study alchemy, the player can have a main string of the most core actions necessary to progress through the game, and add a side string whenever the player chooses to start one of the major non-core portions of the game.

Well, we've had several threads about generalizing interactive story scenes and generating story in gamedev's past, but I don't believe any of those attempted to include linear stories. If you look at the field of "how to write" books there are several formulas or patterns for what an ideal novel or play should be structured like; those of course are only about linear, non-interactive stories because they're not about games.

I think that if you made a generalized set of instructions for creating the story structure of a game, you'd probably have to make it for the most heavily structured game, but then you wouldn't be using 80% of the instructions for a simple linear game. Is that what you want to do?

Check out Inform7 and some of the other related work in that field; should give you some good inspiration and guidance if nothing else :-)