Europe certainly ain't what it used to be. Many are the citizens of Europe that desire a fresh start in the New World. For you, the colonial leader, this means that across the seas there is a free and endless supply of labor. All you need to do is attract 'em, bring 'em to the New World and put 'em to work.
To draw immigrants to your colony, you must generate Crosses. While all settlements generate a meager amount of crosses automatically, to increase the outflow, you can build Church or Cathedral buildings or employ a Firebrand Preacher in either. This will greatly increase the rate at which crosses generate and therefore the number of immigrants leaping at the chance to join your colony.
To see how many crosses you must generate before a new immigrant will appear, you can visit the Europe Screen [F2]. On the Europe Screen, three possible immigrants are displayed in the upper-right. When the immigration bar at the bottom of the screen fills, one of those immigrants will then appear at the Europe Screen docks. If you don't want to wait for the bar to fill, you can also hurry an immigrant by [left-clicking] on his or her portrait in the upper-right of the screen. Hurrying an immigrant does cost a certain amount of gold.
You do not need to bring an immigrant to the New World if you do not need him or her. Multiple immigrants can be found waiting on the docks in Europe and you may select the ones you want. All you need do is send a ship large enough to carry them to the New World.
The 16th and 17th centuries were times of great religious upheaval across Europe. When he nailed his 95 Theses to the door of a German house of worship in the early 1500s, a young monk named Martin Luther challenged the authority of the most powerful religious body in Europe - the Catholic Church. The resulting religious chaos gave rise to innumerable new religious sects, many of whom were shunned - often persecuted - for their nonconformist beliefs. Many of these religious groups found new life across the seas, fleeing to the New World to escape oppression in the Old.