Tim,
Statutory birth, death and marriage registration (in some jurisdictions called Vital Records) only started in Ireland in 1864, save for non RC marriages which were recorded from 1845 onwards. So you won’t find a birth certificate for John if he was born around 1837.
For earlier years you usually need to rely on church baptism records, where they exist. You need to know the precise denomination in order to search the correct records. Not all churches have records for that period and not all are on-line.
RC records are mostly on-line on the nli site:
https://www.nli.ie/en/family-history-introduction.aspx
For other denominations, the churches usually hold the originals but there are also copies in PRONI, the public record office, in Belfast. A personal visit is required to access them. Access to the records there is free. This link explains what records exist, parish by parish:
https://www.nidirect.gov.uk/publications/proni-guide-church-records
You haven’t said what happened to John junior’s parents. If they died in Ireland after 1864 you should be able to get death certificates for them. However the names are both very common, so it’s almost impossible to identify the correct ones without some idea of where they stayed and their occupations. Taking the 1901 census of Ireland as an example, there are 174 John Graham in the county and 172 Agnes/Nancy or Ann Graham (all 3 names are interchangeable). So care needs to be taken not to get the wrong family.
One clue I can give you is that the 1859 Scottish marriage cert should tell you whether John & Agnes Graham (the parents) were alive on 19th May 1859. If dead, it will say (dcd) after their names. If alive, it will not say anything. The Scottish records are pretty meticulous about that. And it should record John’s father’s occupation. Again an important piece of information in ensuring you find the right man.
I’d view John Graham’s date of birth with a little care. Most people in Ireland in the 1800s didn’t celebrate birthdays, nor did they often know exactly how old they were. When officialdom asked for a date of birth, they frequently just made one up. So his actual birth and baptism dates might be a few years either side of the date you have.
There is a tree on Ancestry (Ward/Niederer tree) which has this family. There are a couple of aspects which make me wonder how accurate it is. It has John Graham senior 1805 – 1860, born and died in Armagh. Agnes Agnew 1815 – 1901 born Armagh and died in Co. Antrim. John Graham junior is shown as born Antrim on the date in 1837 you have. He then has 5 siblings born in Carlisle 1838 – 1849, including a brother also named John Graham. Having 2 sons of exactly the same name both alive at the same time doesn’t seem very likely to me. I wonder if this is the right family? England introduced birth certificates in 1837, so it should be possible to verify those births, and the parents names, from birth certificates if you wished to do so. It has Agnes living in Little Bampton, Cumberland in the 1871 English census, followed by her death in Antrim in 1901. I would wonder, if the family lived in Cumberland for at least 30 years whether she did die in Antrim, a county she had little or no connection with. I suspect that’s possibly a different Agnes Graham. I’d have expected her to have died in Cumberland. But perhaps the owners of the tree may be able to clarify where they got the information.
The tree has John Graham b 1837 married twice. First to Ann Donahue 1839 – 1872 and then to Mary Bridget Sheridan 1834 – 1890.