The most important and constant variable when it comes to praying is something called "prayer timeout". When you first start the game, you have a prayer timeout of 300. This decrements by 1 every turn (not every action you take). When it hits 0, it is safe to pray. Praying will generally save you from immediate trouble, like being low in health or starving. It can also take care of minor problems like cursed equipment, but see the following note.
As ires_and_curses points out, if you're using prayer to save yourself from trouble, then you can actually pray before your prayer timeout hits 0. Major trouble can be safely done with 200 or less prayer timeout, while minor trouble can only be safely done at 100 or less prayer timeout.
Upon praying, your prayer timeout will increase by some amount between 50 and 1000, and you'll have to wait until it drops before you can pray again. Note that if you have been crowned by your god for your services, the prayer timeout increase is actually higher. Any item that gives you enlightenment, like a Potion of Enlightenment, will tell you "It is safe to pray" when you are at 0.
If you pray before your timeout is 0, then you will anger your god, and increase the prayer timeout. If you sufficiently anger your god, then you will receive increasingly dangerous punishments, starting with cursed or destroyed equipment and ending with lightning from the heavens being followed by a wide-angle disintegration beam (this is not two separate punishments!). Praying while your god is angry with you will also be bad, you need to pacify the god by making sacrifices before you can safely pray again.
Some other factors that affect when and where you can safely pray, even with 0 prayer timeout. Praying on an altar of another god is going to anger your current god if your alignment is good. Praying in Gehennom counts as praying to Moloch, so it has the same effect. If your luck or alignment is negative, then prayer will not work (though I don't recall if you get punished here). Being a demon and praying to a non-chaotic god will accomplish nothing because the thought disgusts you. Being undead and praying to a non-chaotic god will cause the god to turn you back to living and sustain damage as you return to the natural cycle.
You can reduce the prayer timeout by sacrificing creatures. The better the sacrifice, the better the rewards. Good sacrifices are creatures of the opposite alignment to your god, especially opposing unicorns. This is the only way to reduce the timeout besides waiting for it to naturally expire.