In 1862 there were 38 John Graham's in Fermanagh as head of household's. A total of 231 in Fermanagh. She could possibly be a cousin that marrying a cousin was quite common and she may have gone out to NSW for that purpose.
Griffith Valuation 1862 Fermanagh is used as a census substitute.
Anything before 1864 in Ireland is a parish record. There is one online birth and marriage website but it is a not for profit, fee paying website. About 1844 might raise quite a few John Graham's but worth a look. I would look to his children's boys names for clues to his father's name. It probably is John but not always.
If RC you might find on www.familysearch.org
going to the first page, scroll down to UK-Ireland and then Historial records-Ireland birth 1630-1881 and then enter name and county and best year and see what turns up. Looks like lots of John Graham's and this is where the names of his children would help you find a likely candidate.