Specifically, what makes a story a fairy-story?
According to Tolkien, a fairy-story isn't a story that contains fairies or elves or other sorts of fanciful creatures, the insertion of a fantastical element into our world. Rather, a fairy-story is a story about a world, the realm of Faërie. Middle-Earth and Narnia are examples here.
Tolkien writes:
[F]or fairy-stories are not in normal English usage stories about fairies or elves, but stories about Fairy, that is Faërie, the realm or state in which fairies have their being. Faërie contains many things besides elves and fays, and besides dwarfs, witches, trolls, giants, or dragons: it holds the seas, the sun, the moon, the sky; and the earth, and all things that are in it: tree and bird, water and stone, wine and bread, and ourselves, mortal men, when we are enchanted.That last is key, Faërie is an enchanted world.
What, though, does it mean to accept the invitation of enchantment? Specifically, are we "pretending" when we enter Faërie? When we accept the invitation of the elves are we engaged in "make believe" and playacting? Are we adults indulging in the whims and imaginations of children? Tolkien recounts in his lecture how he corresponded with a man who said that fairy-stories were "Breathing a lie through Silver."
Tolkien's response here is Augustinian. As Augustine famously wrote, our hearts are restless until they rest in God. Faërie incarnates and expresses our desires, informing us about the world we experience and long for. Here is how Tolkien's describes what drew him to the land of Faërie:
I had no special “wish to believe.” I wanted to know. Belief depended on the way in which stories were presented to me, by older people, or by the authors, or on the inherent tone and quality of the tale. But at no time can I remember that the enjoyment of a story was dependent on belief that such things could happen, or had happened, in “real life.” Fairy-stories were plainly not primarily concerned with possibility, but with desirability. If they awakened desire, satisfying it while often whetting it unbearably, they succeeded...I never imagined that the dragon was of the same order as the horse. And that was not solely because I saw horses daily, but never even the footprint of a worm. The dragon had the trade-mark of Faërie written plain upon him. In whatever world he had his being it was an Other-world. Fantasy, the making or glimpsing of Other-worlds, was the heart of the desire of Faërie. I desired dragons with a profound desire. Of course, I in my timid body did not wish to have them in the neighborhood, intruding into my relatively safe world, in which it was, for instance, possible to read stories in peace of mind, free from fear. But the world that contained even the imagination of Fáfnir [a dragon in Norse mythology] was richer and more beautiful, at whatever cost of peril.This argument from desire, for a "richer and more beautiful" world, also features in C.S. Lewis's apologetical works, how his restless search for Joy led him to God.
The enchantment we find in fairy-stories gives voice to our Augustinian restlessness. Our desires point toward the Real. To walk in Faërie is a longing for God.