First, no one is asking you to lie. This isn't about inventing details or exagerrating. This is about deciding how to answer and phrasing your answer.
Second, "story" in this case means personal anecdote, like the author's hiking example. It is not very closely related to stories in books or games or whatever. What can we say about the stories you tell casually at parties or with friends? Probably that they take less than two minutes, they start with an interesting hook, and they include a problem of some kind and the resolution to that problem. That's what your interview stories should look like.
Ex: Suppose you are asked, "Tell me about a time when you had a disagreement with a coworker and how you resolved it". Compare these two answers:
1) "One time I had a coworker that kind of hated me. I'm not sure what his deal was, we didn't interact all that much and I thought his work was pretty good, but he developed a personal animus towards me and started being rude and picking fights with me on Slack. He ended up getting fired after he threw eggs at my car."
2) "I was leading the effort to fix the critical-but-brittle X service, and I wanted to start by wrapping it in a service with modern deploy and test automation, so we could at least deploy it safely while we fixed it. However, the lead architect was opposed to that plan, because of Y. We worked through it by getting all of the stakeholders together and doing Z.
Which answer is more true? The first one might feel more honest. After all, the "disagreement with a coworker" part is much more central to answer 1 than answer 2. But it's also a terrible answer, because it has fuck all to do with your abilities. It's just a thing that happened to you that happens to meet the criteria the question asked for, but is otherwise not relevant.