Under the French Regime it was not a lack of organized government structure but an overabundance of it during the 1600's and 1700's. There were 3 governments (Montreal, Trois Rivieres and Quebec) each with their own governor, intendant and milicia. The records kept in Quebec are a combination of church and notarial records (in those days you did not lend out a cow without having a notary prepare a document detailing the terms and conditions). Although lists of passengers by ship and year do not always exist - there are many that do (ie: Liste Debien, Auger, Massicotte, etc) - these lists were of people who were hired in France to come to the new world - it details all kinds of information including in some cases how much they were paid, the term of their contract, etc. There are many sites that have lists of the ships that came to new france and from notary records you can often find when someone first "appeared" giving an indication as to when they arrived in the colony.
New France was a penal colony from 1722 to 1725 - the practice was discontinued when the bishop and intendant of New France complained to the king to cease the importation of "this sort of people who have no faith and no religion, who are capable of the most horrific crimes and vices ..." - the practice was ended in 1725. For the most part these people were an insignificant percentage of the settlers - the majority of settlers were soldiers, filles du roi (who were orphan girls under the protection of the king and not prostitutes as has often been postulated), poor families, merchants and single men/boys who wanted adventure as "courreur de bois".
Check out this site: http://www.rootsweb.com/~canqc/ressources.htm
for everything you ever want to know on researching french canadian roots.