Conversion by Events
Two random events exist for all countries, that change a settlement's religion to the state religion. All countries may get the event Conversion of Heretics. The second event, Conversion by the Sword, happens only to narrowminded countries (those with innovative at 0, 1, or 2). Additionally, countries with pagan and Hindu state religions have random events that change their state religion and cause conversions in several provinces.
For some countries, scripted events exist that change the religion of some settlements, though not always to their state religion. The major powers tend to have such events, which can be exploited by players who read events files.
Note that event-driven conversions target settlements, which includes cities and colonies. Since colonies can usually be easily converted (see below), it is generally a good idea to send a colonist to each colony with an alien religion that you capture, even if you do not intend to complete the colony any time soon. This will prevent a lucky conversion event from being wasted.
Conversion by events does not change the culture of pagan provinces, so getting one of the events for a pagan province is not always desirable, as you will no longer be able to change the culture of the province.
Conversion by Colonization
Most colonies can be easily and cheaply converted as part of further colonization. Whenever a colonization attempt succeeds, and the colony is not promoted to a city as a result, the colony's religion is set to the state religion of its owner. (Also, the colony's culture is set to the primary state culture of the owner, another very nice effect.)
In other words, via colonization a colony will be converted to your ideal religion and culture, so long as the population of the colony is 899 or less when the colonist arrives there. (Or 799 or less, if natives are present.)
If you do capture a colony with 900+ population, you will probably have to convert it via missionaries. If it is on your home continent, you can do this cheaply only when it is still a colony; of course that means delaying the income from it for a long time if your monarch is not great. If the colony is not on your home continent, then it will be cheap to convert either as a colony or as a colonial city. You might also be able to get its population to decline below 900; see the article on population.
If you capture a colony with 800-899 population with natives, it is generally best to kill the natives so that you can colonize to convert it.
Conversion by Missionaries
Although events may sometimes do conversions, most conversions in the game take place as a result of a country sending a missionary to a city. Missionaries are costly investments in both time and money. But conversions can be well worth the expense, especially in the long run. Recall the benefits of same-religion cities:
How to Send Missionaries
Missionaries may be sent from the main map in one of two map modes: the normal map mode, or religion map mode. Religion map mode may be turned on by clicking the religion map mode button (it shows an icon of a missionary) in the controls window. In religion map mode, the send missionary screen is displayed whenever you select a province. When a settlement is selected, it will display the chances and costs to send a missionary. Assuming you've got the money in treasury, you can dispatch the missionary by clicking the "Send" button.
You can also dispatch a missionary in normal map mode, by right-clicking on the province and selecting the appropriate menu option.
Once dispatched, missionaries require years to produce a result. Only two results are possible: success and failure. On success, the settlement's religion is changed to the owning country's state religion as of that moment (not when the missionary was sent). Converting a pagan settlement has an additional benefit: upon a successful conversion, the culture of the settlement is changed to the owning country's primary state culture. On failure, the residents of the settlement will rise in rebellion, generating a unit of rebels.
Chances, Costs and Time of Missionary Conversion
This section details the chances, costs, and time required to send a missionary. Although there are many factors, most of them are unlikely to change much or at all. However, among the changeable ones, the most important is the monarch's administrative skill. If you have a poor monarch, it's often better to save your money and wait for a better one. One other important factor that can sometimes be overcome is an absence of a land connection: if you can connect a province via land (via further conquest), it is usually better to wait to do conversions.
Conversion Chance of Success
The base chance of converting a settlement is 15%, or 13% if it lacks a land connection to the capital. Countries with pagan state religion receive a special +10% bonus to their base conversion chances. Add +2% per point of the monarch's administrative skill (capped at +18% for ADM 9) and +1% per fortress level in the settlement. Subtract 0.5% per 5,000 inhabitants of the settlement, up to a maximum of -10%.
If a land connection exists, start with a base cost of 100 ducats. To this, add +4d per point of base tax value in the province, and +4d per 1,000 population of the settlement. Finally, there is a distance surcharge of 0-10d, depending on the distance to the capital.
Settlements with no land connection cost roughly twice as much to convert: 175d base, +7d per 1,000 inhabitants and base tax value, and a distance surcharge ranging up to 50d.
Both cases above may be reduced dramatically by a special rule introduced in EU2 1.09: any colony or colonial city (< 5000 population) on a different continent costs a country one-fifth as much to convert.
Missionary conversion is a lengthy process. It is determined mainly by the monarch's administrative skill. The base time is 3 years. Add +1 year for every point the monarch is below ADM 9. Add an additional 1 to 2 months for each province between the settlement to be converted and the capital.