So I am answering it for anyone who is searching for a solution to this problem.
In most cases this problem is because you are trying to execute 32Bit code in a solely 64bit environment.
For Debian Jessie, which is the most current (IBM unsupported) distribution you might take the following steps
Enable installation of 32Bit files (maybe optional)
dpkg --add-architecture i386
The Traveler Setup as of 9.0.1.7 is still 32Bit so needs a few libraries which are not installed by default.
apt-get install lib32z1 lib32ncurses5 (formerly known as ia32-libs)
apt-get install libx32gcc1
apt-get install libx32stdc++6
The Traveler Setup might only work in silent mode. The defaults are quite usable. In many cases you just have to to change the language in the silentInstall file
For german this should do it
./TravelerSetup -f ./installer.properties -i SILENT -l de
This works fine for me but please keep in mind that IBM is not supporting Debian at the server level (but I have been doing this since the first Domino on Linux release and am still alive and kicking).
Have a nice day whoever is still using IBM Domino nowadays.
Henning