It depends what religion you have; later religions are going to be harder to spread. However, you want to first hit civs that do not have a state religion. If you get a single city with a religion they'll switch, and any other religions will have a hard time converting them. Start building missionaries as soon as you have a chance at open borders, one per civ that doesn't have a state religion.
I haven't really gone beyond that, but if you have a neighbor that you want to remain peaceful with that has a different state religion (but NOT a holy city) try to hit every city. Missionaries are fairly cheap so mix them in with unit builds.
Also not that a shrine and temples will help spread your religion, and that your religion will not spread to someone that you don't have open borders with (IIRC). Even if you can't get a missionary, having a temple and open borders gives you a good chance.
I've lately been trying some heavy religion starts, and managed to get hindu and judaism(sp?) even without Mysticism; you take a hit on the military and dev side but limiting the number of other state religions out there helps a lot with happiness.
Also, it is good to focus on a few civs that will be your allies. Try to get ones in the middle of the pack, and well placed (can help you in wars, but not so close that borders will piss them off). Getting religion to the guy across the continent is good, but not nearly important as a nearby neighbor.