What influences the chance of missionary success: whether the city is owned by your team, and how many religions the city has already got.
So to improve your odds... well, if it's an enemy city, you can try capturing it first. That's about it.
Each time you convert a city, the odds of a later conversion drop; so in practice the important thing is to prioritize the religions (state religion, wall street religions, other religions for which you own the shrine, what ever is left).
The probability of converting your own team's city are never lower than 40%; other cities half that. Assuming the game actually matches the code in the SDK, etc.
Reference: CvUnit::spread
Edit: pointed out elsewhere, you can gift your missionary to the AI, and let the AI try to convert its own city for you