dwarf fortress is a game where you make up your own stories tho ;D
Emergent narrative as opposed to an embedded narrative.

I mean, this is a subject that interest me a lot and I could spend a long time quoting books, texts, and master thesis on the subject but I'll cut it short.
Every game is more or less narrative. The difference is between, like I said earlier, emergent and embedded narrative. Like other people said, it all depends on the kind of game you are making. RPGs and other story driven game will need (as a general rule) a bigger narrative drive to get the player going and invested in the game world you created. On the other hand, a puzzle game probably won't need a strong embedded narrative to get you playing, it's more about the system of rules, the gameplay. The experience you are having and that you will be retelling is the emergent narrative, it's your experience with the game as an object. Depending on the genre and the gameplay, you need to gauge how much of the player's experience will come from either type.
After that, we can go and look at how we can pass that embedded narrative, be it through cinematographic language with the use of cut-scenes, through the environment (a good example is the iPhone game Spider) and the use of space (one of my ideas for my master thesis), or through gameplay as some more experimental games tried to do.
This is a more complicated issue than what you think. It's more than a story of "have it or not", it's about how to do it while using what the videoludic and the cinematic (since movies can be integrated in games) language.