До 2-й мировой войны многие беженцы-апатриды (в том числе из Российской Империи) получали Нансеновский паспорт (wikipedia.org), выдаваемый Лигой Наций. Известны случаи, когда с Нансеновским паспортом жили до 70-х гг.
Сейчас апатриды (как правило, это беженцы) смогут пропутешествовать лишь до международной зоны аэропорта или до первой границы (где, как правило, они ищут убежище).
Путешествовать же без паспорта сложно, но можно: например, из США можно поехать в Пуэрто-Рико или в круиз только по водительскому удостоверению. Можно также представить ситуацию, когда лицо без паспорта путешествует на яхте: в международных водах паспорт не нужен, а за водой и провизией можно приставать в те острова, где нет таможни/паспортного контроля (таких много в ЮВ Азии и Карибском море).
У нас в России они считаются лицами без гражданства, сокращенно ЛБГ. Визу в Россию для ЛБГ сделать можно, но они идут по категории миграционно опасные страны.
Я знаю человека, у которого нет гражданства, но имеется вид на жительство в Германии (розовая такая карточка). С видом на жительство и какой-то справкой о том, что он апатрид он может путешествовать по Шенгену.