Every arrest is logged into a database run by the FBI, along with the data (ID, fingerprints, description, arrest records, etc.). I don't think all states/jurisdictions are part of the information sharing program, but the majority are at least, and some of that data is even shared internationally when people go through customs IIRC.
Or they keep local records that nobody looks at or know if they are correct?
Because if it's the first one, kudos for whoever created that system. Plenty of countries fail with way less prisoners/inhabitant.