After installing gem, the command that will work is gem1.8, not gem.
To make gem work, type `sudo ln -s /usr/bin/gem1.8 /usr/bin/gem`
That will create a system link so that the 'gem' command works on its own.
By the way, here's a great article on installing/uninstalling rubygems:
http://www.decentmind.com/2010/05/how-to-uninstall-remove-ruby-gems-on-ubuntu/
