In my case, I was lucky enough to connect with a distant relative who had done a lot of the research, and then confirm parts of it (I was at uni at the time - love a large library and databases!).
Her being a convict helped with the record keeping, of course - court records, ship records, habitation records on the ground. And even by the time she was freed, these were all tiny colonies* so recording everyone was pretty easy.
*How tiny? Well they evacuated the ENTIRE colony of Norfolk Island in about 1807, shipping them all to Hobart which was in need of a larger population. Even then, her daughter (my 7x great grandmother) was something like the 143rd wedding in the colony (now state of Tasmania). Compare that the USA circa 1807 which had 17 states in the union and a population of about 6 million.