Install basics through aptitude

aptitude install ruby ruby1.8-dev libopenssl-ruby1.8 rdoc ri irb build-essential wget ssl-cert

Install newer gems from source

cd /tmp
wget http://production.cf.rubygems.org/rubygems/rubygems-1.3.6.tgz
tar zxf rubygems-1.3.6.tgz
cd rubygems-1.3.6
ruby setup.rb
ln -sfv /usr/bin/gem1.8 /usr/bin/gem

Now update

gem update --system

gem sources -a http://gems.github.com/
gem install capistrano

1. http://wiki.opscode.com/display/chef/Installation+on+Ubuntu+8.04+with+RubyGems
2. http://www.capify.org/index.php/Getting_Started