From StrategyWiki, the free strategy guide and walkthrough wiki

You want to get as many colonists as possible, as fast as possible. There are a few ways of getting them.

You get immigrants if your churches make enough crosses, or if you pay for those crosses. It's the main way of getting colonists at the beginning, but they are often of low quality. Indentured servants should be sent to Indians for education, but petty criminals may be more of a burden than of a value. Get William Brewster to the congress as soon as possible - no more servants and criminals, and you get to select one of 3 available immigrants.

If your scout finds fountain of youth, you get 8 immigrants colonists for free. It's not unusual for this to happen even 2 or 3 times during a game, if you explore a lot and have some luck. I don't think the chances depend on difficulty.

As the game passes, each immigrant costs more and more. Because of that, major church-building programs are waste of time (and the English are not as great as they seem). If you get a Firebrand Preacher anyway, building a Church for him is reasonable. But better think about the economy. I haven't done any calculations on the crosses, but I've seen some suggesting that each colonist in European port reduces number of crosses you get each turn. That's one more reason for getting them out of Europe as soon as possible.

You can get a free colonist for 200 food in any of your colonies. It's a slow way, but you're likely to have big food surplus, so why not do something useful with that food. It's usually more practical to move all the food into central cities, far from Indians, so it's converted to colonists faster, and the Indians won't steal it from you (and they can even give some food to you).

Paying for educated workers at the Royal University is the right thing.

• Get an Expert Ore Miner and clear his specialization. Free colonist for only 600 gold. That's the way of getting colonists in the later stages of the game. Then you then train him in whatever profession you want.
• Ore Miners, Lumberjacks and Gunsmiths are so cheap, than getting them there is more efficient than training them in the colonies. Silver miners too, mostly because you only need a few.
• The rest, except for the last four, are in reasonable 950-1300 price range. It may be cheaper to get them trained instead of training them yourself, especially if you need a lot of them quickly.
• You need at least one colonist with given profession to teach others. Expert cashcrop farmers can only be taught by the Indians, everyone else you can get from the Royal University.
• Veteran Soldiers are unbelievably expensive. Get a free colonist for max 600 gold, arm him (arms are cheap early, you'll be making a lot at the colonies later), give him horses (you'd have to even if he was from the Royal University), and attack some Indians. With George Washington, he will be promoted if he wins (and only lose 50 cheap horses if he doesn't). That way you can get almost 3 veteran soldiers for the price of one from the University.
• Elder Statesmen are very expensive, but sometimes necessary. Teach your statesmen if you can (unfortunately University is required).
• Jesuit Missionaries are a waste of time. With Jean de Brebeuf all missionaries function as experts, even the petty criminal missionaries.
• Firebrand Preachers aren't very useful either. Immigration gets more expensive with each immigrant, so their value diminishes quickly.

You can get a few colonists by conquest or by Indian conversions. Converts aren't very useful, except for early game. Bartolome de las Casas turns all your converts into free colonists, but that's just a one time action.

Other powers develop so slowly that you wouldn't get enough colonists from them even if you conquered all their colonies. But small attacks here and there are a good extra source of colonists.

If you combine all strategies - a few churches, paying for immigration or at the Royal University, search for fountains, Indian converts, food conversion, and conquest - you will get flooded by the colonists, and with proper education and organization you can expand at astonishing rate.

[edit] Prices at the Royal University

Generally Schoolhouse skills are cheapest, and University skills are most expensive, but there are some exceptions (expensive Farmers and Soldiers, cheap Gunsmiths). Exact calculations in the next section.

Veteran Soldiers get free 50 muskets (at price 6 it means 1700 for Soldier itself) and Pioneers get free 100 tools (at price 4 it means 800 for Pioneer itself), so their "real" price is lower than their listed price.

600	Expert Ore Miner	Schoolhouse level
700	Expert Lumberjacks	Schoolhouse level
850	Master Gunsmiths	College level
900	Expert Silver Miners	Schoolhouse level
950	Master Fur Traders	College level
1000	Master Carpenters	Schoolhouse level
1000	Expert Fishermen	Schoolhouse level
1050	Master Blacksmiths	College level
1100	Expert Farmers	Schoolhouse level
1100	Master Distiller	College level
1200	Hardy Pioneers	Schoolhouse level
1200	Master Tobacconists	College level
1300	Master Weavers	College level
1400	Jesuit Missionaries	University level
1500	Firebrand Preachers	University level
1900	Elder Statesmen	University level
2000	Veteran Soldiers	College level

[edit] Value of education

Because we know price of a Free Colonist (600), prices of already educated colonists, and time needed to teach them (4,6 or 8 turns, depending on level), we may calculate how much is teacher's time worth.

Value of Muskets (6*50=300) and Tools (4*100=400) at some arbitrary price level has been subtracted from Pioneer's and Soldier's prices.

In early game, when colonists are cheaper than 600 gold, teaching is worth even *more*.

Value generated per turn:

0	Expert Ore Miner
25	Expert Lumberjacks
41	Master Gunsmiths
50	Hardy Pioneers (depends on price of Tools)
58	Master Fur Traders
75	Expert Silver Miners
75	Master Blacksmiths
83	Master Distiller
100	Master Carpenters
100	Expert Fishermen
100	Master Tobacconists
100	Jesuit Missionaries (actually 0 after Brebeuf)
112	Firebrand Preachers
117	Master Weavers
125	Expert Farmers
162	Elder Statesmen
183	Veteran Soldiers (depends on price of Muskets)

For comparison (on good but not ideal terrain):

32	Fur trapping (32 tons, 1 gold/ton)
72	Tobacco planting (18 tons, 4 gold/ton)
120	Silver mining (8 tons, 15 gold/ton)

As you can see, teaching can be extremely profitable (or to put it other way, paying for training extremely unprofitable).

In particular, start training your own Expert Farmers, Expert Fishermen and Master Carpenters as soon as you can (Schoolhouse is cheap, and few other professions create 100 or more gold of value per turn), then Master Blacksmiths in College, and Elder Statesmen as soon as you build a University.

Expert Ore Miner, Expert Lumberjacks, Master Gunsmiths and Hardy Pioneers can be bought - their education is not that valuable.

Veteran Soldiers seem like their education is worth a lot, but that's not really true, as you have a third source of them - Washington and attacking Indians.

[edit] Immigrants to select first

Seasoned Scouts and Hardy Pioneer are probably the most useful. Expert Farmers and Fishermen are also very important to have, especially since one such colonist can teach others.

You need specialists in your cash crop. The only feasible way of getting them at that point is taking either a free colonist or an indentured servant immigrant and sending them to the right Indian village.

Get Brewster as soon as possible to improve quality of your immigrants.