My wife is a geneaologist. Birth certificates, marriage licenses, election registrations, death certificates and other means of identification were regularly issued from Day One.
The originals were usually maintained at the county court house, but handwritten copies were provided to the individuals for signature (usually achieved with a "mark", as many folks didn't now how to write).
I believe we have Benjamin Franklin to thank for this procedure. He was the first county clerk.
But that didn’t answer my question. How did you determine if an immigrant was legal or illegal? If the definition of “jurisdiction” depended on that then didn’t they have to have a way?