Acho que você só precisa instalar o RubyGems para:
sudo aptitude install rubygems
(ou busca no synaptic para rubygems)
Ok, acabei de reconhecer que não há RubyGems > 1.3.7 no repositório do Ubuntu (o Debian na verdade tem um sid em 1.6 ...). Então você precisa instalá-lo no site .