Their marriage was before the start of statutory registration of marriages in Ireland, so to find them you need to rely on church records, where they exist. To do that you really need to know their exact denomination, together with their townland or parish.
Griffiths valuation will show you where there were Cully households in around 1860. (There were about 30 in Co Armagh). If you have no other leads you could start searching the parish records for each of those households. (The relevant parishes are shown on the Griffiths website).
The 1901 census has 106 people named Cully listed in Co. Armagh. Broadly an even split between Presbyterian and Church of Ireland with the occasional Baptist and RC.