france
How is this possible? How can there not have been some sort of central
authority keeping track of this, especially if it's not only illegal
but an extremely serious crime? Were the different (even nearby) USA
"states" so extremely detached as to not share this kind of basic
information?
Other answers and comments have focused on the technology aspect, but it is primarily an issue of government organization and legal rules, rather than one of technology.
This wouldn't have happened in France, even in the 19th century (i.e. post-French Revolution after marriage laws were standardized in the French Civil Code and in related bureaucratic centralizing reforms initiated by Napoleon). There, all of the marriage and divorce and name change records of a person are maintained at the local clerk's office of the local government in the place you were born, and there is no counterpart to the notion of "common law marriage" that exists in a few residual common law jurisdictions including a number of U.S. states.
This old fashioned paper records in a file cabinet method worked because each person had only one designated file cabinet. If you tried to get married under a false name and the local clerk's office where the person of that name purported to have been born didn't have a birth certificate for that person, the marriage would have been promptly annulled by operation of law even if no one complained, and a fraud investigation would have been commenced.
Likewise, if a French citizen got married a second time, without the proper paperwork showing that their existing marriage had been terminated by death or divorce filed with the local clerk's office in the place that they were born, the marriage would also have been annulled by government officials even if no one complained, and a bigamy prosecution would have been begun as a matter of course.
In a sense, this method of personal record keeping was even decentralized. There was no single central databased of birth, death, marriage and divorce records for most of French history, although there may be one now in very recent times developed long after WWII.
But, while the record keeping was decentralized, it was still highly coordinated in an efficient pre-modern bureaucratic system.
The Japanese family registry system of the late 19th century and beyond would have been similarly effective and efficient in a low technology era by similar means (except that polygamy wasn't prohibited there until after WWII, so this particular problem wouldn't have arisen).