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:
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.)