Registration didn't begin until 1869. Church records would be your best bet.
On Caroline's marriage rego it says she was born in Marmora and they are living there in 1871.
Valentine's wife was born Ontario according to census so they likely married in that province.
From 1871 census I would say they married c 1864/65.
Did not find them on 1861 census but 1851 they are still in Quebec.
1842 census Argentuil there is a George Tennason, labourer. No ages or place of birth given. He is in a place with 6 other inhabitants but whether they are family or not, it doesn't say.
Too bad they weren't Catholics and then they are a lot easier to track before registration.
On Weslayen Methodist Baptism I found a Mary Jane Tennyson, father George, mother Mary Maria was christened in Madoc Tsp Hastings County 18 May 1862, born 23 Apr 1862.