The Ainulindalë is the name of the first part of Silmarillion. It is the creation story of Tolkien's Middle Earth, and demonstrates that this Secondary World's cosmology is thoroughly monotheistic, proceeding from the one God, Eru, who is benevolent and skillful at turning evil--represented here as the discord of Melkor--into good. It is well known that Tolkien was a devout Catholic; given this bit of his biography, it has struck many readers of The Lord of the Rings as odd that religious beliefs or practices don't show up in the story.
In fact, I can think of just two places in the story which have explicitly religious content.
The first occurs in the chapter, The Window on the West, behind the waterfall which Faramir and his men use when patrolling the land of Ithilien, a narrow strip of land running north-south, bordered on the west by the River Anduin and on the East by the Mountains of Shadow, wall of the realm of Mordor.
Before their evening meal, "Faramir and all his men turned and faced west in a moment of silence. Faramir signed to Frodo and Sam that they should do likewise. 'So we always do,' he said, as they sat down: 'we look towards Númenor that was, and beyond to Elvenhome that is, and to that which is beyond Elvenhome and will ever be."
That which is "beyond Elvenhome" is probably, at least, Valinor, the land of the gods, or Valar. But as we learn in the Silmarillion, these gods are really more like super-powerful angels, participating in Eru's creation and ongoing care for the world. We might surmise, but it would be only a guess, that the people of Gondor look "beyond" even Valinor, to the ultimate origin of everything: Eru.
The second explicit religious reference in the Lord of the Rings, in "The Siege of Gondor," is rather different. Denethor, Steward of Gondor, has given himself over to despair at the hour his people need him most. Eager for news, he tried to make use of one of the seeing-stone, a palantir. But Sauron controlled the palantiri and was able to poison Denethor's mind with images of death and despair. Also, his son Faramir has been gravely injured in a foolish battle ordered by Denethor himself. Denethor is overwhelmed by guilt and grief, but in his despair he decides that he must take his own life and his son's:
"Better to burn sooner than late, for burn we must [...] I will go now to my pyre. To my pyre! No tomb for Denethor and Faramir. No tomb. No long slow sleep of death embalmed. We will burn like heathen kings before ever a ship sailed hither from the West. The West has failed. Go back and burn!"
The use of the word "heathen" here feels a little discordant, at first glance, anyway. A heathen is usually understood to be someone who follows a false religion, and/or is very low moral character. The term really only makes sense in a religious context, and implies that the one who uses the term to describe others is himself religious, a follower of the acceptable or correct religion.
So Denethor seems to be saying that at this dark hour he will be abandoning the righteous funerary practices of Gondor, which involve embalming and entombment after a person has died, and will instead embrace a different practice of burning himself and his son alive. He's not just doing a wicked thing; he's doing something sacrilegious, and he appears to know that, and embrace it.
These two snapshots from the book offer very little indeed for making a case that religious belief and practice matter to the story of the Lord of the Rings. But I don't think we should rely only on these two explicit religious references. Additionally, we need to attend to the Elves to get a fuller picture of the religious atmosphere of the book.
The most striking elvish activity recorded in the book, which might be construed in a religious way, is the hymn to Elbereth which Galdor and his companions sing as they walk through the Shire. Elbereth is one of the elvish names for Varda, who is one of the Valar. She is the creator of the stars and his the spouse of Manwë, lord of the Valar. If Eru is God and so the First-Ranked, Manwë would probably be number two and Varda number three. So Elbereth is a Big Deal. Here is the hymn:
Snow-white! Snow-white! O lady clear! O Queen beyond the Western Sea! O Light to us that wander here Amid the world of woven trees! Gilthoniel! O Elbereth! Clear are thy eyes and bright thy breath. Snow-white! Snow-white! We sing to thee In a far land beyond the Sea. O stars that in the Sunless Year With shining hand by her were sown, In windy fields now bright and clear We see your silver blossom blown. O Elbereth! Gilthoniel! We still remember, we who dwell In this far land beneath the trees, Thy starlight on the Western Seas.
This beautiful poem praises Elbereth as the Queen of the Stars. She is a light to us wanderers. She is "beyond" the Western seas but also her starlight is "on" the Western seas. Wherever in nature there is gold or silver, especially in the leaves of trees and in flowers, the elves see her handiwork.
As a Catholic, it is impossible to read this hymn and not think of the Blessed Virgin Mary. She has several "titles" which suggest a close association, including "Star of the Sea" and "Queen of Heaven." "Snow-white" traditionally symbolizes purity, and Catholics believe that God kept Mary "immaculate," that is, free of any stain of sin.
Catholics, of course, do not worship Mary as God. They venerate her. So, here in the book, are the elves worshipping Varda, or merely venerating her? It's hard to say; we're not given much to go on. I lean toward the view that they are merely venerating her, since some of the highest elves in Middle Earth personally conversed with the Valar before the breaking of the world, and would have known better than to give the worship due to Eru to one of his angels. But either way, once we know who Elbereth is--Varda, Queen of the Valar--we cannot deny the religious nature of this hymn. They're not singing about a beloved ancestor. They're praising the maker of the stars.
There is of course much more to be said, both about Varda herself and other glimpses of divine things in the Lord of the Rings. But the point I want to make here is that the creation story offered at the beginning of the Silmarillion does a big part of the work of validating these religious readings of Lord of the Rings. The world in which that story takes place is the very world which Eru created through the mediation of the Valar. The Elves carry with them a deep sense of reverence for the Valar, some of them (e.g., Galadriel) even with memories of living face to face with these gods before departing their realm forever to hunt the stolen silmarils.
The elves don't "evangelize" in any sense, but the people of Gondor, as descendents of the noblest and most "elvish" of all Men, the Numenoreans, retain traces of this ancient knowledge of the gods beyond the sea. Frodo himself calls out the name of Elbereth when he is attacked by the Black Riders on Weathertop, and Aragorn comments that the saying of that powerful name probably did more to protect Frodo's life than any of his other efforts in the skirmish. All this to say, devotion to the gods, and by extension, to God, is not something reserved only for the Elves, even if it is they who bear the deepest religious sensibility of the three races (Elves, Men, and Dwarves).