Programming wise that isn't that hard. Even if the story doesn't branch on major plot points little things like the order in which you visit rooms or solve puzzles can change the order of events enough to make the player feel like they are affecting the outcome.