Acts 22 sees Paul about to be scourged by Roman soldiers until Paul interjects that it is unlawful for a Roman citizen to be scourged. The soldiers and tribunes seemingly take only Paul’s word, at least that is all that is mentioned in the text, on the matter and immediately cease with his punishment, for fear of punishment themselves.
Paul was obviously a learned man, able to write and speak Greek, but he was also a Jew in Roman territory, just like the crowd which initially got him almost scourged. The swiftness with which the Roman soldiers attempt to scourge him suggests that they naturally assumed he wouldn’t be a Roman citizen.
How did one prove citizenship in such situations? Are there other examples beside the Acts of the Apostles that we can go off of?
In 62 BC, Cicero gave a speech defending a friend of his, a poet by the name of Aulus Licinius Archias. Archias claimed to be a Roman citizen, although born in Antioch, because he had been an inhabitant of Heraclea, whose inhabitants had been granted citizenship en masse after the Social Wars. Sadly, the register office of Heraclea had burnt down during the war, and he had been out of town during the last few census - Archias was forced to use the town preator's private records and the endorsement of several town notables to prove his citizenship.
While this might have changed some by the time of the early Empire, the broad outline would be the same; there would be town registers, every official would keep their own records, and, finally, there was your own reputation as a citizen.
Sources:
Mary Beard's SPQR, p240.
a translated copy of the speech