Early Canadiana Online
Early Canadiana Online is a digital library with "2,198,626 pages in 13,825 volumes" and counting. The interface is available in either English or French. For several hundred of their non-U.S. dollars you can gain access to all the databases, but the free collections may be all you need. Whether your ancestors were French, English, or Native, you'll find historical documents that give context to their miserably cold lives. Searching for your Canadian surnames—or the names of your ancestors' hometowns—can produce some interesting results, but don't expect to find your family tree laid out and adorned with red maple leaves.