There are several components to this:
1) What role does religion play in the fantasy society you are designing?
2) What role do clerics (of whom the player character may be one) play in the society, and in the religion? Likewise Paladins, Druids, Monks, etc.
3) What is the metaphysical/theological/magical basis of the religion? In a fantasy world, religion *works*, but how often and how well?
4) What role does religion play in the life of Clerics (Paladins, Druids, Monks)?
5) What role does religion play in the life of PCs without religious classes?
For Ancardia to meet your laudable-and-achievable desires for immersion and replayability, these questions need to be answered coherently and with internal consistency. If Clerics are the only NPCs who have religious-blessings, why can a non-Cleric PC get them? If there's a wide pantheon of Gods who give out colorful and unusual powers, there should be NPCs running around who worship them, with more or less corresponding powers, and so forth.

I'll go ahead and make suggestions:
1 & 2) A big one. Clerics and Druids are trusted professionals, and needed for the survival of their communities. In medieval europe, it was thought: every village needs a priest, or you can't go to Mass every Sunday and you'll all go to hell! In Ancardia the need for a Cleric is unarguable and pragmatic - you need a Priest to bless the graves or the dead get up and go on a rampage. So, the world generator should know this:
* if a town doesn't have a cleric in it, NPCs in the town should ask you to deal with the undead problem they invariably have.
* a sizeable share of settlements should be monasteries or cathedral-towns; nearby settlements may be feudal dependencies.
* if you have NPCs on circuit, cleric-troubleshooters would be a good start.
There are clearly at least two organized churches - a Church of Law and a Church of Chaos. There may be others, of course. Characters should be able to be members of these organizations and this should matter.
Related to this - Clerics have religious and spiritual training. Thus, they can consecrate ground, they can imbue things with purifying power, and so forth. I'd suggest: this doesn't *actually* have anything to do with faith or religion per se. So a Cleric can be a member of the church of Law, and can be Chaotic Evil. Only a few saints *actually* derive any benefit from their depth of conviction. So Clerics may usually be religious, but they can be false in their religion and it doesn't impair their mojo to any major degree.
If you view Clerics as people who are trained to protect people from spiritual threats, I think things hold together much better than the Nethack/D&D system. This is more in line of what actual folkloric religion was like, after all.

3) You can have a piety relationship with more than one God - and in order for you to have secretly-evil clerics (and Cardinal Richelieu is such an awesome villain, why give him up), you can't have an Altar of Law shoot thunderbolts at anyone secretly-evil who makes an offering. So for this to hang together the Gods need to chill a notch, and religion needs to be at-least-partially decoupled from alignment.
Other than that, it seems that stuff done at altars usually works. I'd suggest that altars in civilized hands should demand cash payment for use (like the Dwarftown Forge) unless the PC is a member of the corresponding religion (which presumably requires both at least a few cleric levels and a quest.)
Incidentally, for replay value it might be cool to randomize up either the pantheon (so there are different Gods with different agents and patronage powers each time you play), or to randomize the political relationship among the religions and their relationship with the plot. So, for example, in some games it could turn out that the chaos gate actually needs to be *open*, and the forces of Law have jammed the Chaos gate shut and that's the problem. Would that mean Lawful orb guardians? Anyway it's worth a thought.

4+5) I'd suggest the following states of Religiosity, which are more or less the same for :
* Observant. You can observe more than one religion, which basically means you can use their altars. If you are a cleric (or anyone else with skill ranks in Imbue?) this means you can use their symbols. This requires a positive piety relationship only.
* Patronage. You can only have one patron - possibly there are easy ways to switch patrons *within* a pantheon, if you want to have that make a difference. You get certain blessings from your Patron, in exchange for keeping certain restrictions.
* Sainthood. If you are promoted to being a Saint of your patron, that means you can't change Patrons again without pissing your current Patron off. Saints require more severe restrictions, and actively attract hostility from enemies and rivals of their patron. So if you are Saint of Lord Shalud of Law, when you are wandering the wilderness Screaming Mimies of Xiombarg will sometimes show up and challenge you to mortal combat.
* Champion, a.k.a. Crowning. This leads to the whole "if you change alignments you fall from grace" thing. Champion is the highest level of religious commitment and is meant to be more-or-less permanent.

Anyway, hope those suggestions are helpful. Get Arcane magic working before worrying about all this :).