Religion is always a delicate topic. It's unfortunate that in most novels, it's treated with a very heavy-handed approach. Religion in speculative fiction seems to fall into one of: thinly-disguised Christianity, flat-out corrupt and evil, Gaia-worship, or non-existent.
Which is a shame - because religion will tell you so many things about a society's values and the context of a character. It's an area rich with potential for developing interesting philosophies and concepts. And creating a religion isn't that difficult (hello, Hubbard.) - it's just a matter of looking at how things interconnect.
Most religions are based on either the worship of a being of greater power than ours - Christianity, most forms of Wicca, Islam, Buddhism (sort of) - or tenets of faith (Taoism). In our natural world, it is easy to find 'room' for a supreme being who can perform miracles - we can't (yet) raise the dead, walk on water, feed thousands with a loaf of bread. But if magic is an everyday occurence, how is your supreme being to impress anyone? What makes them special?
The spiritual side of a culture stems from questions it can't answer - either why something is the way it is, or why certain things should or shouldn't be done. Which means that, for cultures that have 'magic' to explain things, the questions will be very different - perhaps far more existential, or philosophising. Faith is also a form of social contract, an understanding that certain kinds of behaviour are and aren't acceptable. It helps form a common ground between people, something of yourself to recognise in another, a way to bridge our innate xenophobia and build communities.
Your religion and your culture should mesh - one should feed the other. If one culture is invading another, often the religions will blend - take Christmas Day, for example. A winter solstice celebration converted into a christian holy day to pull the pagan invadees into the flock. There should be echoes or reverberations between your culture's values and your religion's. Western culture, which is largely christan, abhors murder, disloyalty, someone taking what they didn't earn - and unsurprisingly, you'll find those reinforced throughout the christian faith.
How to build a religion
Religions are generally composed of a few key concepts:
- A supreme or superior being of sorts
- this being may not be actually sentient (it may be 'the universe' or 'the collective consciousness' for example)
- nor may it necessarily possess actual powers (see Chinese reverence for ancestors)
- A set of instructions of correct observance of faith
- may include rituals, rules and ceremonies
- may be a series of "things to live by"
- may just be "these are the basic rules, work the rest out so it makes sense to you" a-la Wiccan faith
- Some kind of reward for the faithful
- does not necessarily have to be in 'the next life' - the reward may be seeking an enlightened experience in this one
- may just be avoiding punishment
Creating religions without these elements is certainly possible - and perhaps more interesting - but make sure you're doing so because it fits the society, not just because you think it would be 'cool'. Unless you're building your society around a religion that has no supreme being, no reward, and no instructions. I'd strongly suggest only trying to break one of those at a time, though.
Also keep in mind that most religions are highly interested in keeping their followers - which means intolerance for other religions is automatically packaged in. ("Thou shalt worship no God but me" etc). This occurs most often in religions that have institutionalised themselves - that is, they've formed churches with dedicated priests who lead a congregation. Typically, these religions gain power from both the size of their congregation, and the donations of their followers, so building a large faith-base is crucial. Religions that are on a more 'personal' level - where there is little need to gather for worship, such as Taoism and Wicca - tend to have less intolerance of other beliefs built into the system. Not that the individuals may be tolerant or intolerant, but rather, it's not ingrained into the structure of the faith itself.
Which leaves you one of four main questions to answer first, to create your religion - is this a culture with public gatherings or faith, or is belief a private affair? Is there faith and trust in a superior being, or a more isolated, self-reliant base? Are there instructions - is it highly ritualised, or based on each individual's interpretation of the guidelines? And - what kind of reward are they working towards, if any?
Obviously if you world or culture disobeys standard physical laws - if the dead return or communicate easily, people are immortal or godlike beings regularly descend to the world, the structure and balance of belief shift accordingly - an entirely different set of questions arises. But the crucial aspect is to ensure that when you are creating a world, you consider the ramifications of a decision across the whole range of the cultural experience.