How were ancient Roman citizens identified, and how did officials make sure that their identity wasn't fake? I.e., did they maintain some kind of citizens registry, or did they have some kind of identity papers (analog of modern ID card, driver's license, passport, etc.)?
I don't have a good citation for this - the wikipedia article provided by @kubanczyk is relatively decent, and highlights the role of the censor, which is probably the state oriented solution to the question.
I think the question relies on modern assumptions. Roman citizens would never have needed to prove their identity. Set aside for the moment the urban tribes - they're really just a special case. - and let's set aside women, because that is probably a book length answer.
Every other Roman citizen is bound in a fairly strong social context; they're a member of a family, a tribe, and a gens. Furthermore most Romans were a member of some kind of a patron-client relationship.
Remember also that there are sumptuary laws and customs that determine clothing/costume. Also remember that your legal rights and obligations are based on your social class. For anything other than the lowest social ranks, you are effectively required to participate in the state, and your participation is defined by your social class/citizenship status. Anyone with any ambition is on the cursus honorum, which has the effect of creating a reputation throughout society. If the individual is not actively on the cursus honorum, then they're goign to want to ask a favor or provide a favor to someone who is on the cursus honorum.
Roman society is bound together by a web of relationships, and that web serves as such a strong evidence of citizenship that there is no need for any kind of proof. Anyone who had any doubt about an individual could easily ask someone for a report on their reputation. Anyone who didn't have a good reputation would be unable to act politically, economically, socially, etc.
Update: Mr. Goldberg raises another interesting edge case (apart from women and urban tribes). What about Romans travelling abroad? This is a slightly different set of questions. 1) How do Foreign governments determine whether someone is a Roman citizen? 2) How do Romans determine if someone is a Roman citizen.
In truth, I believe that the answer remains the same. Despite the fact that Roman society invented the rule of law, neither Roman society nor any other society of the period practiced the rule of law. The rights of an individual arise first and foremost from their social network and only secondarily from any legal status. If Egypt (or Armenia, or Persia, or whoever) takes action against an individual, that action is legal unless the individual's network imposes consequences. Mr. Goldberg poses the perfect case - Verres execution of a Roman citizen. If Verres had not pursued justice for his lictor, then nothing would have happened. If Verres had not been over the top, he wouldn't have been brought to trial.
Rome had no police force, no agency charged with enforcing the law (There were specific forced devoted to enforcement of laws against arson, and against treason, but that takes us into book length territory; I'm making a concious generalization). The responsibility for enforcing the law fell on the kin, tribe, gens and patron of the offended individual.
Update 2: Voitcus cites the example of St. Paul who asserts that as a Roman citizen he has the right to be tried in a Roman court (by the Caesar). Paul is an interesting case because he was an itenerant preacher, a member of a persecuted minority. In fact, part of the reason why Christians were persecuted is that they didn't fit neatly within the mold. Paul could be simultaneously a Christian, a Roman citizen, and a Jew. (Discussion of what it means to be simultaneously a Jew and a Christian are out of scope for this question). Based on my memory and quick research, we don't have a great deal of facts concerning Paul's alleged crimes, or his accusers. He seems to have offended the local Jewish population. His offenses against Judaism should have been tried in a court in Jerusalem. Paul asserts his right as a Roman citizen and demands a change of venue to a Roman court in Rome, which we may infer would be a less hostile court.
Unfortunately in order to discuss the issues that Voitcus raises, we'd have to know more. We don't know if Paul's claim was challenged. If it was unchallenged, then Paul never needed to prove his claim. (the local authorities may have felt that getting him out of town would resolve the local problem.) I would assume, based on my study of Roman history, that the local authorities had already consulted Paul's relationships and reputation and knew him to be a citizen.
Most probably, if an official wanted to make sure what is the man's name, they asked them. Honest man has no reason to lie in this case.
The list of citizens was maintained, mainly for tax purposes. It was updated during a census, an event when each father of family had to appear in person and provide all the details under an oath and before witnesses. Wikipedia section.
I think that the modern practice would be considered humiliating by Romans. Innocent, honest citizens of today are obliged to prove to the officials their identity, as if their words were insufficient. The burden of proof should be obviously on the officials, since most people are honest and innocent.
The most common document identifying a person in Ancient Rome was diploma. Diploma identified the powers of magistrates and other office holders, including the consuls.
Regarding the asked question, Roman citizenship of discharged soldiers if they had no citizenship before service was identified by a so-called military diploma
The diploma was a notarially certified copy of the emperor's decree.
An example of the text can be found here:
These diplomas certifying citizenship were issued to ordinary people who earned citizenship as well, according to Suetonius:
According Suetonius, there were important requirements needed for the diploma to be valid, so to combat falsifications. They were imposed by the senatorial decree:
Although all the above answers are relevant, there is one facet that has been overlooked concerning the provincial citizens. As Roman citizenship was granted to non-Romans in the provinces, the provincials had to reaffirm their citizenship every five years.This was simply a stating of their name and of the type of citizenship they had. (Rome had several levels of citizenship, with each level having different perks).