I have found 2 shrines so far. The one to Azura (which is on the map that comes with the game, and not too hard to find...) Azura gives you a special soul gem.
I just found the shrine of Sheogorath under St-Delyn (in the canalworks? anyway, at the bottom-most level of St-Delyn in Vivec.) I must say the gods do give interesting quests. I will proceed to finish this quest after my pesky university graduation ceremony tonight...
I would appreciate more info/hints on where to find the other god shrines.