As a penal colony nsw was governed by the Royal navy. The british settlements at Sydney Cove and Norfolk Island were guarded by the marines. In 1796 the Royal NSW Corps or'Rum Corps'- soldiers from the Savoy military prison in England - was formed to take over from the unhappy marines. In January 1810 the 73rd Regiment of Foot arrived with Lachlan Macquarie to clean up the problems left by the Rum Corps. I believe the 73rd Regiment has a data base online. Up until 1870 there were 25 British infantry regiments and a couple of artilliary units.I have never heard of a convict being recruited to any of these British units. The last british regiment left in 1870. Despite so many British troops in the Australian colonies, colonial military forces were maintained from as early as December 1788, Phillip Gidley King,on Norfolk Island ordered his 6 free male settlers to practise musketry on Saturdays. In September 1800,Governor Hunter asked 100 FREE male settlers in Sydney and Parramatta to form English volunteer units because he was scared of the Irish Rebels just transported into the colony. Convicts stopped arriving in NSW in 1840 so there wasn't a need for a lot of military.
I suppose all these regimental records are in England.

Hi Thanks I was well thinking the same about convicts and service, however some information I have found on http://freepages.history.rootsweb.ancestry.com/~garter1/Largest%20military%20marriage.htm has an ancestor RICHARD PALMER who married Elizabeth TITLEY

so hence my confusion.

Ill keep digging :)