Statutory registration of births only started in Ireland in 1864 so for any births prior to that year, you’ll need to search church records for baptisms. To do that you really need to know which parish they lived in.
There’s only 1 birth registered in Ireland for a Justin Madden in 1864. That was registered in Dublin South, Volume 7, page 751. So that could well be your family. I’d be inclined to get a copy of that birth cert to see where the couple were living. You could then use that information to locate their parish and search the parish records. Assuming they were RC, copies should be held in the National Library in Dublin.
Here’s Justin Madden in the 1901 census. He has pulled off the clever trick of being recorded in the same census twice. Once at home and the second time at work. (Bakers worked at night so presumably that accounts for him being listed at his place of work):