まず、readlineをインストールしておく。

$ sudo aptitude install libreadline-dev

rubyをダウンロードして展開、--with-readlineを付けてconfigure、make、sudo make install。

$ wget ftp://ftp.ruby-lang.org/pub/ruby/1.8/ruby-1.8.7-p174.tar.gz
$ tar xzvf ruby-1.8.7-p174.tar.gz
$ cd ruby-1.8.7-p174
$ ./configure --with-readline
$ make
$ sudo make install

rubygemsのインストールについては以下を参照。
ruby、rubygemsのインストール