This is more about how various aspects of storytelling might interact with other aspects of your world’s culture.
Where does legend and myth end in your world, and history begin?
This is a question that you do need to consider. The answer matters on many different levels. For one thing, it can be influenced by the kind of people you’re writing about. Typical humans may forget the true events in a few hundred years, so that an anecdote that sounds better and more dramatic has come to substitute for the “boring” historical events. If you’re writing elves, who typically live hundreds of years and are represented as having very good memories, it may take several thousand years, and at least one event that damages their records, for them to forget.
On another level, the answers to various of your story’s riddles will depend on what is true, what is imagined to be true, and what is outright false. A lot of fantasies pull the trick of, “Surprise! They’re alive!” where a certain non-human race or evil foe thought to have been banished centuries past returns. In some novels, this works rather well. I was able to get a sense from the uncertainty of the stories that there was a strong possibility that the evil or the non-humans might return. Or else, there are certain people alive who remember the truth, even if no one else does, and know the reasons such a return is likely (Tolkien chose this route). But some fantasy has such a strong disjunction between history and myth that the author couldn’t convince me. Either the characters who had thought elves were mythical all their lives accepted them without so much as a blink, or the author had tried to pull a trick like people forgetting the entire truth and making something else up after only twenty years, which is silly. Try to make sure that your stories that are meant to inhabit that tricky ground between myth and history actually sound like they could be there, and not like they ought to be true or ought to be false.
On a third level, distortion is fun. Perhaps the figure your people now worship as a god was perfectly mortal in his lifetime, and while they’re all sitting around waiting for him to come back and save their asses, he’s not coming because he wasn’t immortal, and they won’t recognize their true savior in time. Perhaps the “sword” that they think the hero will wield was actually some other kind of weapon, changed to a sword because it sounded so dramatic, and nobody can find it because everybody’s looking for the wrong thing. Let enough time pass, let the winners write the history books, and villains can become heroes and vice versa. Janny Wurts uses this as an interesting conceit in her Wars of Light and Shadow books, where the character worshipped as a god of Light has a very different personality from a god’s in real life.
And finally, you should know the truth, or be very good at coming up with plausible explanations in the middle of the story. Your characters not knowing if unicorns really exist or not can add to the fun. Your not knowing can make the story wildly self-contradictory, and not so much fun.
Are religious stories thought of differently than “fairy tales?” How many categories of tales exist in your world anyway, and what kind of prestige do they have in the eyes of the people who tell them? In some societies, a priest relating miracles of his god is going to get the kind of respect that the old witch babbling about the Fey Folk just won’t.
Of course, there’s no necessity to make your religion’s stories of any one particular kind. A lot of fantasy religions, even the ones not specifically based on Christianity, take parables as their models and think that religious stories must teach moral lessons. Not necessarily. What moral lesson do you draw from the Greek tale of Philomela, for example, who was raped by her brother-in-law Tereus? He cut her tongue out so she couldn’t tell anyone, but Philomela wove the story into a tapestry and sent it to her sister, Procne, Tereus’s wife. Procne killed their son, Itylus, and served him to Tereus for dinner. In the end, the gods changed Procne into a swallow and Philomela into a nightingale.
Yes, perhaps it’s, “Don’t rape people” or “Don’t cut up your son and serve him to your husband for dinner.” But it’s a lot less clear-cut than something like the parable of the talents.
Experiment with your myth cycles. Don’t just make creation myths and parables and nothing else. How do your gods interact? If you have a monotheistic society, how does its god relate to his people? Is there a difference between special, chosen mortals, like priests, and the laity? What about non-human races, or intelligent animals like dragons (if dragons are intelligent in your world?) A structure like the Greek myth one allows for a variety of relationships, some that “explain” nothing more than a particular god’s choice of a symbol.
Don’t assume your religious stories have to be retellings of natural phenomena or disguised dogma. There’s a lot of fun to be had there.
Lots of fantasy authors do have creation myths somewhere in their stories, because most fantasy authors don’t deal with scientific cosmology in their stories. They could, though. For example, what happens if you have a society where science is the province of a very few, much like it was during the Renaissance, and the majority of people are suspicious and frightened peasants? Surely they would make up stories about what they believed the scientists to be doing?
They don’t all have to be a variation of “black sabbats,” though that was one of the most popular stories in our own world: that scientists were black magicians in league with the devil. Perhaps your world doesn’t have a convenient devil-figure or dark god to hang the stories on, in which case you’ll have to plan something else. Maybe a discipline in the halfway ground between science and magic exists, like alchemy, and the way most people explain science is a muttered, “Crazy alchemists!” and a wave of the hand. Maybe there are specific stories for each scientist in question. (Hey, wizards manage to acquire those in a lot of fantasy worlds). Perhaps the scientist is thought to get advice from non-humans, who could be considerably more advanced, and accepted as considerably more advanced. Perhaps the peasants view the scientists as more akin to holy men.
Or perhaps science isn’t in ivory towers at all, and is out among the people. You should still make up stories about it. There isn’t, or shouldn’t be, a section in each culture labeled “science,” where study of the natural world sits in sterile isolation while everyone carefully tailors their words around it. If nothing else, turn to anecdotes. What funny or fascinating things do scientists do and say, perhaps while arguing with their colleagues, that get remembered?
Magic gets remarkably little storytime in fantasies to itself. It’s usually there in the form of a magical sword or talking animal in a creation myth, just like our world. But unlike our world, in a fantasy one magic does actually exist, and few fantasy worlds make it so rare that a lot of people have to talk about it by hearsay instead of real-world experience. Why not give it a section to itself?
How do people relate to it? If they break magic up into several categories, perhaps the tales of white magic are heroic and those of dark magic fearsome. Perhaps it’s seen as appropriate to have wizards invoking it, but any bard who tried to sing of a peasant hero taking up a sword would get stared at. (I wish I could send those staring peasants after fantasy authors who insist on trying to resurrect the tired ‘the peasant boy is actually the secret royal heir’ plotline).
Fear needs more stage time. One thing that irritates the hell out of me about the way fantasy authors approach magic is that it’s basically shadow-boxing. There are all kinds of warnings about the immense and terrible things that magic did at one time- usually vague tales about a wasteland- and worries that the teenie hero’s magic is about to get out of control. But any magic cataclysm is averted, and the teenie gets training in time.
Let magic get out of control sometimes. If you intend it to star in your world’s equivalent of horror stories, or if it should because it’s so powerful and so dark, then have more horrific things happen than the creation of a wasteland that happened so many years ago most people no longer care.
Two authors who do this wonderfully are Terry Pratchett and Simon R. Green. Pratchett uses dragon-calling magic in Guards! Guards! A secret society summons a dragon that they think will be under their control, except that it’s not, and the dragon is turned loose as a fire-breathing, hungry predator in a big city. Blue Moon Rising by Simon R. Green uses the Darkwood, a haunt of demons, and Green lets the demons actually come out and kill people, including all the inhabitants of a small mining town in one of the most spectacularly creepy scenes I’ve ever read in fantasy. The tales of the Darkwood and the tales of the dragon are ones that, you feel certain at the end of those books, are going to live, and scar people.
If magic is a natural force in your world, and a powerful one, let it do more than create ancient wastelands and fling fireballs around at an opportune moment. What is it doing the rest of the time?
Wish there was more science in the books I read lately. And fewer teenie heroes.