On the 1861 census, the family is living in Smiths Falls, in Lanarak County and they are listed as Church of England.
I believe there was only one Anglican church at that time and there is still one. Smiths Falls is in the Anglican Diocese of Ottawa. You can contact the Archives at the Anglican Diocese of Ottawa and I believe they will search for a marriage in 1856 for a small fee. There might also be burials and baptisms as well.
At that time, Anglican marriages did not have to be reported and the only records are either in the parish or the Diocese archives.
http://www.ottawa.anglican.ca/Contact_Us.html#archivesYou might want to post under the board for Ontario, Lanark County as well for more precise information about Smiths' Falls. The library might have more information.
Good luck.