In his Wikileaks statement Edward Snowden says that the US government
“has unilaterally revoked my passport, leaving me a stateless person”
This is a common misconception. A passport is evidence of nationality, but it does not confer nationality. All states have laws that operate to confer citizenship on certain people, usually on the basis of place of birth (‘jus soli‘) or descent ‘jus sanguinis‘), and sometimes a combination of the two. Whether a person does or does not hold a passport has no bearing on whether these laws confer citizenship on the person.
Here in the UK we have rather complex citizenship laws that, for example, confer citizenship on children born in the UK to a settled parent and also to children born abroad to a parent who is a British citizen. We also have several categories of non-citizenship nationality. It is a horrible mess. But not having a passport, or even having it withdrawn or revoked, does not necessarily mean you are not a British citizen. I’ve even come across cases where British passports have been issued in error and it turns out the individual is not British and has no right to the passport.
Sometimes a non citizen will apply for citizenship, a process often referred to as ‘naturalisation’. At that point a certificate of some sort is usually issued as proof of grant of citizenship and the person can then also apply for a passport. The naturalisation application and the passport application are separate processes.
Think about it. No child is born with a passport already issued. Those children are not stateless. Similarly, it seems that only around a third of United States citizens hold passports. The rest aren’t stateless, they just haven’t got a passport.
However, not holding a passport does make it rather difficult to travel as most countries want to know who you are and that you can be removed somewhere else before they will admit you.