According to Sherwin-White's The Roman Citizenship:

"The only documentation in the Republican period was the registration of the young adult citizen in the tribal lists that were drawn up and revised at Rome by the censors every five years. Municipalities kept their own local lists also, which acquired the validity of censorial lists when a law of 44 transferred the census to the magistrates of the Roman municipalities, who were required to register the citizen population with their full names, patronymics, and tribes, and with a schedule of their property."

Apart from local lists however, there would have been other ways to prove citizenship, especially as Roman citizenship began to be extended to more and more people. Again, Sherwin-White says:

"Formal documentation of the grant of citizenship to provincial soldiery appears first in 89 B.C., in the shape of a bronze tablet recording the decree of a proconsul enfranchising a unit of Spanish cavalrymen in the Social War, who are all named in a general list. Presumably each soldier received a copy. The cities of persons of higher status enfranchised by Octavian in c. 40 B.C. received a copy of a decree detailing all the privileges of their new status, while his auxiliary veterans could acquire copies of the enabling edict that enfranchised them. But it is only with the regularization of the grant of citizenship to the all time-expired auxiliaries by Claudius that a standardized document appears. This is the small bronze diptych known as the diploma civitatis, containing a brief and uniform formula conferring the Roman citizenship on the holder and his descendants, who is indicated by his name and military unit. These documents were not normally used for civilians, who received instead a copy in libellus form of the brief imperial warrant authorizing the registration of their enfranchisement in the archives at Rome.

Diplomata and libelli provided for new citizens. For the mass of the citizenry, for whom censorial registration at five-yearly intervals was an inefficient instrument, adequate provision was finally made by the creation of an official system of compulsory birth registration under the social legislation of Augustus (A.D. 4). The Roman citizen was required to register the birth of his children within thirty days before a Roman official, and he received a wooden diptych recording the declaration, which acted as a certificate of citizenship for the child for the rest of his life. Like the military diplomata this contained the names of seven witnesses, and provided a presumptive proof of citizen status. Similarly the enfranchisement of freedmen, which depended upon a formal act, was recorded in a documentary tabella manumissionis. Citizens of diverse origins thus came to have some form of documentary evidence of their status."

It isn't surprising that these records of citizenship would have changed. After all "in the case of Rome, though the details are obscure, Roman citizenship clearly developed in dialogue with the citizenships of other Latin communities" (OCD). Keeping track of so many people becoming citizens would have been quite taxing on the state, and consequently the Roman census remained incomplete. It should also be noted that by the time of Caracalla, virtually all of the free population of the empire was granted citizenship in the so-called Antonine constitution. However by this time the right to vote had long disappeared; provincial Romans had lost their exemption from taxation; and many of the most important personal privileges of citizenship had been restricted to the elite. And thereafter the essential distinction was between slave and free.