When looking for something completely different, I just discovered that this is now online free at

http://www.
collectionscanada.gc.ca/databases/census-1871/001101-100.01-e.php

Search results are linked to digital images of the census enumerators' books.