First priority is a city that is not already a holy city. This is the only one I can confirm with every game I've played so far.
Next, I think the city with the least number of founded religions is choosen. So if I have 2 cities, Athens and Sparta, and Athens has Hindu and Judaism while Sparta has Christianity, and I discover Confucius, then Sparta will get it. I am not certain of this, I haven't played enough games to confirm.
After that it's random. Say I have 5 cities that aren't holy cities, the game will select one at random. If all my cities are holy cities, and each only has 1 religion founded in it, then it's random for the next religion.