It's definately not purely random. Do this for example: Found a religion while you have only your capital, which makes it the holy city. Then found a second city, and research another religion tech - and the new holy city will always be your second city, never the capital again. Then found a third city, and research yet another religion tech first - and again, the new holy city will always be your third city, never your capital or your second one.
-Kylearan