After reading this question few questions popped up in my head. I know what a stateless person is after I read this wikipedia page but I could not find how do stateless people travel? if stateless people have no nationality then logically they have no passport.. if they do not have passport how do stateless people travel?
The UK Border Agency has a page describing just this, including how to apply for travel documents if one was stateless.
They note that:
A stateless persons' document issued to an adult will usually be valid for 10 years if you have permission to stay in the United Kingdom permanently (known as 'indefinite leave to remain'). If you have temporary permission to stay in the United Kingdom (known as 'limited leave to remain'), your stateless persons' document will usually be valid for the same period as your permission to stay here, up to a maximum of five years.
In addition they point out that if granted, a stateless persons' document is normally valid for travel to all countries.
Indeed, since 1954, you've been able to obtain a '1954 Convention Travel Document' which for all intents and purpose, acts as a travel document, like a passport. Indeed, it says 'travel document' on the front cover. This arose from the 1954 Convention on Stateless Persons.
Countries provide travel documents for citizens of other countries, or stateless persons. These documents are called "Laissez Passer" (French for "Let through").
Usually, Laissez-Passer holders are required for visas to any country.
Jews from many countries were forced to renounce local citizenships when they wanted to immigrate to Israel. Some of those countries (like Iraq in the Wikipedia example, or more recently - Soviet Union) provided Laissez-passer's to these Jews, valid for travel to Israel.
Israeli Arabs traveling to Saudi Arabia were (and may be still are) using Jordanian travel documents, because they cannot use their Israeli passports in the Saudi Arabia.
People working for international organizations (UN, Red Cross, etc) have travel documents issued by these organizations. Some refugees (stateless persons) have travel documents issued by international organizations as well.
Many countries issue travel documents to people resident there who are either 1) stateless, or 2) unable to get a passport from their country of nationality. It is usually called "Certificate of Identity", "Alien's Passport", or "Re-entry Permit", depending on the country. This article talks about the many forms of such documents. It could be a 1954 Convention travel document, but a lot of countries are not signatories to the 1954 convention; they may still have such a document.
Such travel documents are in booklet form just like passports, with a biographical page and pages for visas and stamps. Not all countries accept such travel documents, but many do.
(Note that, if the stateless person is also a refugee, they can usually get a "Refugee travel document", which is technically a 1951 Convention travel document.)
We do not travel. We cannot. Like myself, stateless persons have no legal identity, so it has become almost impossible since 9-11 for us to get through all the paperwork and list of requirements needed for any travel document.
Many stateless persons can not travel within the borders of the country they call home because they lack "official" documentation. We can be held at any time, for any amount of time the authorities deem necessary to establish our identity.
The truth is there are very few countries that will accept a stateless person. If a stateless person is found within the borders of most countries they are placed in a "detention" center and usually forgotten about. This is, of course, in first world countries like the US and Canada. In third world countries we are basically turned into slaves with no rights to anything.