All the info on propaganda can be found in the editor. The chance for propaganda is modified by two things:
1) Overall culture. The chance to convert a city ranges from 30% if another civ is "in awe" of your culture to 3% if a civ is "disdainful" of your culture.
2) Governments. The more advanced your government is, the worse it does in terms of propaganda. For example, Democracy gets a 30% bonus when using propaganda against a city in despotism. This is unusually high though; most of the ranges are around 10% for government. For example, if you are communist trying to convert a city under republic, the chance is -10%.
I believe the overall chance is simply these two added together. Note that even under the most optimal conditions (democracy vs. despotism, "in awe" of culturally) the chance is only 60%. Most of the time, the odds will be around 20-30%, which is the reason why it seems to work so little. If you have less culture than another civ, it's almost impossible to use propaganda successfully.
Also note that cities under a democratic government are immune to propaganda.