I couldn’t get readline to be picked up using the ‘rvm package install readline’ command. So instead I had to install the readline development headers as a Debian package

sudo aptitude install libreadline6-dev

And then tell rvm about the /usr directory when installing ruby

(Note: I had run ‘rvm package install zlib’ and ‘rvm package install openssl’ before running this next command)

rvm install 1.8.7 -C --with-zlib-dir=$HOME/.rvm/usr --with-openssl-dir=$HOME/.rvm/usr --with-readline-dir=/usr

This solution should also work for Ubuntu.