If you are trying to worship an active god off the wizlist, in most cases it's a good idea to pray from their shrine. That said, not all of the gods have shrines. Their help files should say whether or not they do. Some help files even give hints on where the shrines are. You should find them out IC, and probably not via a note to the immortal in question.

If you are worshipping a god that you've made up or just under a sphere, it's not a bad idea to send a note to 'immortal' and give them the heads up on what you're looking for. Otherwise, just keep prays IC about it and be creative!

Good luck!