As Sporniket said above, one possibility is to have multiple outcomes - ie, the choices of the player affect the outcome.
This would increase the workload quite a bit in determining plot. Multiple outcomes/choices means multiple paths and more writing. This does also have the benefit of increasing replayability however, since the player can play again and make a different choice.
Alternative to this is to consider multiple paths to the same outcome. This would mean less writing in terms of storyline, but still a greater portrayed freedom to the player. As a very basic example; In order to progress the player needs to cross a river, get through a locked door, and past a troll. He has a rope, a golden key, and an axe.
1. He uses the rope to cross the river, unlocks the door with the key, kills the troll with the axe
2. He uses the rope to cross the river, smashes his way through the door with the axe, bribes his way past the troll with the key
3. He fells a tree across the river with the axe, unlocks the door with the key, sets up a snare to trap the troll with the rope
4. He fells a tree across the river, ties the rope to the door - and a boulder - then pushes the boulder off a cliff to yank the door open, he bribes his way past the troll with the golden key.
5. He uses the key to pay for a ferry to take him across the river, smashes his way through the door with the axe, sets up a snare to trap the troll with the rope
6. He uses the key to pay for a ferry to take him across the river, ties the rope to the door - and a boulder - then pushes the boulder off a cliff to yank the door open, kills the troll with the axe.
This shows the same three items, in the same three scenes, used in a multitude of options. The key to not feeding the player the story is to allow the player the essence of choice, even if those choices prove essentially meaningless. If the player has a choice between climbing a wall, or going through a gate, then it seems better to the player even if they both (eventually) lead to the same point inside the castle.