「ruby no such file to load -- readline (LoadError)」でぐぐったら最初のページに答えが書いてないか。

ttp://dirk.net/2009/04/05/no-such-file-to-load-readline-loaderror-when-running-scriptconsole/

まず libreadline をインストール
sudo apt-get install libncurses5-dev
sudo apt-get install libreadline5-dev

そのあと ruby のソースで、readline 拡張ライブラリをコンパイル＆インストール
cd /usr/src/ruby-1.8.7-p72/ext/readline
ruby extconf.rb
make
sudo make install

これを試してみて。