There are few problems in programming that can be solved with one standard answer. Programming is all about solving problems, and the solutions vary from problem to problem. Implementing story into your game is really probably one of the easier things to do. There is little advanced math or logic, the main issue is not really the implementation of your ideas, but coming up with what you want your story to be about. How in depth you want to go into story telling is up to you, and there are many different ways to go about it, which is why it is hard to pin point a logical standard solution.
Here are some examples that I can come up with for story implementations, just to get your mental juices flowing about how you may want to go about this:
Your story is about a zombie survivor out in the woods alone, moving from abandoned cabin to cabin, scrounging for food and ammunition. The zombies could strike at any minute, so you must work fast to be ready for an attack.
How do you do this in programming? Perhaps you have a list of the cabins(probably stored in an array, list, or in some sort of "level file"). The game interprets this data and virtually assembles the level around you. When you walk in the houses and you collect the items, it would remove from the inventory of the house in you "level file". Everything stored has an X and Y position and in your class that handles rendering it would recognize data from the file and interpret that to draw the objects in the house.
Perhaps if you want a story with less player determination, you could play a short animation at the beginning of the game that shows them their fate of eternal zombie battle unless they find the mad scientist that is controlling the minds of the poor undead. You could pick up clues scattered around the game that when touched, would pause your main loop and display an image file associated with that clue. Throughout the game, the player may have to make decisions that will either lead them to the scientist, or keep them battling the zombies. At the end of each "level" of battle, the decision would have to made (either physically in game or maybe in a GUI or something...) and the decision would either put them off track on some random level or bring them closer to the mad scientists lair. Think about how the levels are connected as a tree or a web, not the normal sequential approach.
I'm not expecting you to use either one of these stories, but I hope that gives some idea of how you might plan about things.
For both of these implementations, or anything you come up with, your going to want to use Object Oriented Programming(OOP).
This answer is probably more of the story writing side of things than the technical examples than you wanted, but in reality, it's important to think about what you want something to be, before you're already half way done with it and just sloppily piecing other people's code snips together. What you really need is not a technical answer from us, but a good cup of you favourite warm beverage, a lot of paper and pens, and some time to think about each system in your game, what it does, and how it interacts with the other systems to form a nice, well organized piece of computer art.
As my 8th grade wood shop teacher always said: "Proper planning prevents poor projects".
Stay gold, Pony Boy.