Wow that's a good one. There was a diety write up someplace that listed all that each diety does so you can sort of look through and see which is best for your class. They all have different things so some are better for priest some are better for fighter ect.... I think I looked it up on wiki I'll see if I can find it. Anyhow once you pick the one you want you find the person that starts it there will be a series I think of 5 or 6 quest at different levels the further you go the more stuff you can get from your alter. Your final quest will give you an alter. We also have all the alters in the guild hall. You give the alter items and it increases your fortune (or whatever they call it) with your diety you can then pick certain spells and put them on your hotbar I think iirc they are only good for 2 uses then you have to go back to alter and get them again. I forget what is best for mages I mostly have fighter, and scouts. Maybe someone with some mages can pipe up what is best for them.
On the Butcherblock docks right at the edge of a tent near the steps down into the water there is an NPC that will discuss Deities with you. I still talk to him from time to time even though I have chosen my deity because I like to read his dialogue.
One thing to note is that some gods are good only, some are evil only, and some are neutral. Everyone has a "best for this class" opinion, but I prefer to go for the one that makes the most sense story wise since I solo. You get a pet, a cloak (useful at lower levels), and some spell options (the heal is a good backup panic button at lower levels).