Library and Archives Canada: The vast bulk of information of genealogical interest can be found at Library and Archives Canada (www.bac-lac.gc.ca), which has a wealth of online resources and good research guides. In general the Provincial Archives have a broader range of information relating to their particular areas. Some of the Provincial Archives now have excellent websites with very good immigration information. New Brunswick is an excellent example See Chapter 8 for more detail.
Civil records: Responsibility for registration of births, marriages and deaths rests with the Provinces. The records have widely varying starting dates. Some are to be found on FamilySearch, which has a comprehensive account of years and locations at familysearch.org/wiki/en/Canada_Vital_Records, but many are still held by local registration authorities. Census records: Countrywide censuses are available for 1851, 1861, 1871, 1881 and 1891. There are, however, many local returns available for earlier years, which record a wide variety of information. The largest collection is in Library and Archives Canada.
Other sources: Cemetery and burial records, gravestone inscriptions, passenger lists, church registers and land records may all be of value. A good comprehensive guide is in Angus Baxter's In Search of Your Canadian Roots (3rd ed., 2000), which gives details of a wide range of records to be found in the National and Provincial Archives.