Shirley,
I just meant to say that, if he is in the 1901 census, it will tell what year he came to Canada (or thereabouts). Then you would have a more specific time frame in which to search for details about his arrival.
For passenger records, I don' t know what years are covered by microfilm, etc., but if any are available, it would help narrow down your search if you have a three-to-five year window instead of 20 years.
Have you checked these sites:
http://www.theshipslist.com/ships/passengerlists/index.htmhttp://www.immigrantships.net/It is very hard to find ship records in Canada that far back. I don't know what might exist in England.
If you know what religion he was, have you contacted the church(es) he might have attended in Canada? Perhaps his death record at the church might tell when he came to Canada. His newspaper obit might say how long he'd lived here.
If he was a farmer, did he fill out a Land Petition? My 3rd-great-grandfather's land grant application (in New Brunswick) gave a bit of information. Some give more information, some give less.
I don't know if any in Nova Scotia are available online in 1870+. These are earlier ones but there might be someone you can write to about ordering microfilm or to find out if they are indexed:
http://www.gov.ns.ca/nsarm/databases/land/This is the front page of the website:
http://www.gov.ns.ca/nsarm/Have you contacted the library in the area where he was married? If they have city directories leading up to 1870, perhaps they might find his name listed. That would give you some clues.
You could search the Kings County census of 1861 to see if he was there yet (or request a look-up). Perhaps the local library or genealogical society might have it indexed already. Again, this would give you an idea of when he might have shown up.
Good luck & Merry Christmas to you, too.
Josephine