I think it very unlikely that you would find a birth certificate for as early as 1833 in New Brunswick. Your best hopes are a record of baptism, or a census record. In both cases, an exact location would be needed; and in the case of the baptism, the denomination.
The reference to a marriage in Kingston brings to mind Kingston, Kingston Parish, Kings County, New Brunswick, but that is by no means certain. Assuming a connection to Kings Co., I note in the 1851 census of Hampton Parish:
James Fitzpatrick age 44, Irish, came to NB in 1831, tenant farmer
Mary Fitzpatrick 44, Irish, came to NB 1831
Francis Fitzpatrick 18 b. NB
Thomas Fitzpatrick 15 b. NB
Maria Fitzpatrick 8 b. NB
No William, and the child b. ca. 1833 was Francis. James might be the same, age 29, a labourer, who arrived in Saint John, NB from the port of Dublin, Ireland in MAY1834, a passenger on the ship, 'Edwin'. Apparently single.
A John Fitzpatrick petitioned for land in Kings Co. in 1844. This doesn't mean he got it, just asked for it.
While I see much evidence of the name in Saint John Co. about 1900, I see little evidence of the name in Kings Co. The 1861 census for Kings Co., NB might be worth consulting, and the interlibrary loan department of your library may be able to assist; but it would be wise to fix on a specific location first. The Marriage Registers of Kings Co. are also on microfilm. The census reels probably would have to be loaned from the National Archives of Canada; but the Marriage Registers would probably be at the Provincial Archives of New Brunsick.
Also at:
http://boards.ancestry.com/mbexec/message/an/surnames.fitzpa...is the message:
Hi! I am looking for a Michael Fitzpatrich, born c 1830, unsure where, married Eleanor McAuley in New Brunswick, Canada in 1855; sailed to New Zealand with McAuley family in their brig 'Our Hope'. Anyone with information/suggestions, etc
This message is four years old, but perhaps Stephen has learned more since.
Thomas