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.