While under French rule, land was distributed based on the seigneurial system. The King would grant land to important people or military officers. This made the grantees 'seigneurs' who had the ability to grant pieces of their land to tenants.
When the Treaty of Paris in 1763 gave Britain control, Quebec was divided into counties. These were sub-divided into townships, which were further divided into lots and concessions. Land, known as Crown Land, was then granted to new settlers in lot/concession parcels.
In 1789 Land Boards were established to handle settlement in the districts of Hesse, Nassau, Lunenburg and Mecklenburg which became part of Upper Canada in 1791. Many of the early settlers were displaced Loyalists.
In 1867 the British North America Act transferred responsibility of Crown lands to the provinces (Quebec, Ontario, Nova Scotia, New Brunswick & Prince Edward Island).
In 1872 the Dominion Lands Act was created to encourage settlement of the west (Northwest Territories, Manitoba, Saskatchewan, Alberta & British Columbia). Crown land was surveyed and any male over the age of 21, or any female head of household, could apply, pay a $10 fee, and receive 160 acres. The settler then had three years to clear at least 40 acres and build a house.
In 1930, the federal government transferred responsibility for Crown Lands to Manitoba, Saskatchewan and Alberta.
The federal government kept only the records for Upper & Lower Canada. All other land records were the responsibility of the province or territory and might be found in the province/territory archives.
Some province-specific land records (more may be available on the Provincial GenWebs):