They were married in Australia in 1855. (Given their age difference and marriage in Australia, they may well have eloped). Mary Waldock would have been 20 when she married, so my guess would be they left Scotland in 1854 or 1855, possibly 1853.
Often need to investigate other records to identify Mary on the shipping records. According to Mary's death registration, she was born c
1837 so not 20 years of age when she married. Do you have their marriage certificate? Were either of them literate?
Death
WELSH Mary
Father David WALDOCK Mother Clira McKENZIE [Possibly Christian/Christina]
At Yan Yean 1909 72 years Reg#3569
Possibly her parents' marriage
http://www.familysearch.orgWALDOCH David
McKENZIE Christian
27 Mar 1820 Gorbals, Lanark, Scotland
1841 Census living at Kirk Street South Side No 2, Kirkfield, Lanarkshire
WALDOCK Christina 40 years Sawer [?Sewer] Born Lanarkshire
WALDOCK David 10 years Born Lanarkshire
WALDOCK John 8 years Born Lanarkshire
WALDOCK Mary 3 years Born Lanarkshire [
Born c1838]
CALDWELL Margaret 30 years Needlework Born Scotland
1851 Census living at 24 Drygate Lane, Glasgow
GRAHAM Francis 19 years Barber [employing two men] Born Glasgow, Lanarkhire
GRAHAM Mary 20 years Barber's wife Born Glasgow, Lanarkshire
GRAHAM Susan 1 year Barber's dau Born Glasgow, Lanarkshire
WALDOCK Mary 15 years House Servant Born Glasgow, Lanarkshire [
Born c1836]
And here is Mary with an incorrect age, arriving Victoria on the
BIRMAN with the
GRAHAM family. She didn't elope with Dundas
WELSHhttp://www.rootschat.com/links/01gpj/GRAHAM Francis L 21 JAN 1853
BIRMAN B 028/001
GRAHAM Mary Mrs 22 JAN 1853
BIRMAN B 028/001
GRAHAM Robert I JAN 1853
BIRMAN B 028/001
GRAHAM Susan 2 JAN 1853
BIRMAN B 028/001
WALDOCK Mary 13 JAN 1853
BIRMAN B 028/001
Cando