This makes the gem command work:
sudo apt-get install rubygems1.8
But more is needed...
sudo apt-get install curl ruby
We already have Git installed; if you don't you may want to throw a git-core in there. (And if you already have curl installed, you can leave it out of the apt-get command-- or put it in, it will work either way.