First of all, we all know that it is nearly impossible to found a religion ourselves in higher difficulties, since the AI has a great advantage, such as research, especially at the beginning. Diplomacy in high difficulties seems always narrow down to clashes between a few prominent religions, until Liberalism (free religion) is well adopted by every Civ. If one makes good use of religious diplomacy, victory of all kinds is not very far away.
Here are a few AI’s behavior patterns that I observed (mostly on Emperor and above, Terra or Pangea). Hopefully they are useful to you:
1) Due to AI’s rapid road paving / missionary production efficiency, Buddhism and Hinduism usually becomes 2 prominent religions of the world, before the other religions are even founded.
Usually after the early phase of expansion, one would end up with having strong Buddhism and Hinduism neighbors. Then it becomes obvious — pick one of the two religions, make good friends and trading partners, and expand towards the other.
The religion modifier goes as high as +8 on religion-minded leaders, such as Cyrus, Isabella and Mansa Musa. Isabella is particularly a fine religious ally, as she is aggressive enough to agree to war against civs of a different faith with you. Mansa Musa, on the other hand, would only agree if you give him multiple expensive techs.
2) During peace times, AI always switch to “Organized religion” to make us of its 25% building rate bonus in cities with the state religion. This civic is very nice indeed, and all you need is Monotheism, which you can easily trade from the AIs.
3) Sometimes one religion spreads so fast that every single civ in the world is in the big family, and they are usually happy among each other, much happier than to the player’s Civ. This is not going to last forever, though… (see below)
4) The AI tend to switch religion to the one founded by itself, but usually comply with the international trend until a war breaks out between another civ of the same faith. This is quite important, as when you attack a Civ of the same faith, you would get -1 “You declared war on our friend!” modifier from all Civs of the same religion. But you won’t after it switches to its own religion.
While the AI is losing the war and its own holy city. It will again switch religion to match the environment. Too late!
5) While generally speaking, leaders of the same religion almost always become good friend over time, it is possible to bribe the expansion-minded (and falling in tech) leaders to go against civs with the same faith since ancient times. Some examples are:
- Montezuma of Aztec
- Genghis Khan of Mongol
- Alexander of Greece
- Victoria of England
- Tokugawa of Japan
Chances are some of them are on the map. This means even if everyone is everyone’s friend, I can still stir a world war. Leaders will convert to their own founded religion, causing even more conflicts and military actions promoted (in secret) by nobody else than the player him/herself.
6) Peace loving leaders are extremely reluctant to go after anybody who shares the same religion with them. This means that you don’t have to produce army during peace times when you are bordered with them only. Also, when you attack their neighbors, you don’t have to worry about backstabbing because they can’t choose which friend to help.
7) If there are multiple war-loving leaders (such as Montezuma and Alexander), it is quite important to keep them busy with somebody else as early as possible. They are like mercenaries, waiting for a bid. Even if they are pleased with you, they will still go after you if they have nothing to do with their neighbors.
8) Whenever possible, bribe AIs to war is a great idea even if it costs you your most advanced techs. Every single war put a -3 modifier on relationship permanently, so you are pretty much guaranteed of a life-long enemy between the two, which is a great thing to you. They won’t come after you now, and you can come after them while they are exhausted.
However, you have to have a tech lead relative to them in order to bribe them. In order to have a tech lead, you have to have larger, juicier lands to start on, and good strategies to make money fast. There are many good posts here covering these aspects.
9) Aligning with the No.1 Civ, or the No. 2 Civ (while you are No.1) is not necessarily a bad idea when you are still not prepared in terms of military. Bribe someone to attack them as soon as possible, though. They will give you that -1 “You brought as a war ally!”, but they are usually still pleased with you since you share the same religion. 
10) If you are not using a Creative leader, during the very early game, you probably want to delay the declaration of a state religion so non-capitol cities with non-state religions can have their border expanded to level 2 (harvest diameter) first.
No state religion:
Holy city of any religion: 5 culture / turn
City with any religion: 1 culture / turn, it stacks up
With state religion:
Holy city of state religion: 5 culture / turn
Holy city of non-state religion: no effect
City with state religion: 1 culture / turn, plus 1 happiness
City with non-state religion: no effect