I installed rubygems1.9.1 on a pretty clean Lucid VM.
$ sudo apt-get install rubygems1.9.1
...
The following extra packages will be installed:
irb1.9.1 libreadline-ruby1.9.1 libreadline5 rdoc1.9.1
Suggested packages:
graphviz build-essential rubygems-doc
The following NEW packages will be installed:
irb1.9.1 libreadline-ruby1.9.1 libreadline5 rdoc1.9.1 rubygems1.9.1
0 upgraded, 5 newly installed, 0 to remove and 85 not upgraded.
...
Get:1 http://archive.ubuntu.com/ubuntu/ lucid/main libreadline5 5.2-7build1 [147kB]
Get:2 http://archive.ubuntu.com/ubuntu/ lucid/universe libreadline-ruby1.9.1 1.9.1.378-1 [15.2kB]
Get:3 http://archive.ubuntu.com/ubuntu/ lucid/universe irb1.9.1 1.9.1.378-1 [66.9kB]
Get:4 http://archive.ubuntu.com/ubuntu/ lucid/universe rdoc1.9.1 1.9.1.378-1 [125kB]
Get:5 http://archive.ubuntu.com/ubuntu/ lucid/universe rubygems1.9.1 1.3.5-1ubuntu2 [191kB]
Fetched 545kB in 7s (76.2kB/s)
Selecting previously deselected package libreadline5.
(Reading database ... 29331 files and directories currently installed.)
Unpacking libreadline5 (from .../libreadline5_5.2-7build1_amd64.deb) ...
Selecting previously deselected package libreadline-ruby1.9.1.
Unpacking libreadline-ruby1.9.1 (from .../libreadline-ruby1.9.1_1.9.1.378-1_amd64.deb) ...
Selecting previously deselected package irb1.9.1.
Unpacking irb1.9.1 (from .../irb1.9.1_1.9.1.378-1_all.deb) ...
Selecting previously deselected package rdoc1.9.1.
Unpacking rdoc1.9.1 (from .../rdoc1.9.1_1.9.1.378-1_all.deb) ...
Selecting previously deselected package rubygems1.9.1.
Unpacking rubygems1.9.1 (from .../rubygems1.9.1_1.3.5-1ubuntu2_all.deb) ...
Processing triggers for man-db ...
Setting up libreadline5 (5.2-7build1) ...
Setting up libreadline-ruby1.9.1 (1.9.1.378-1) ...
Setting up irb1.9.1 (1.9.1.378-1) ...
Setting up rdoc1.9.1 (1.9.1.378-1) ...
Setting up rubygems1.9.1 (1.3.5-1ubuntu2) ...
Yet, bizarrely:
$ gem1.9.1 --version
1.3.5
$ cat /usr/bin/gem1.9.1
#!/usr/bin/ruby1.9.1
...
I'm not really sure if this is a packaging problem or a Ruby problem.
I need Gems > 1.8 to install another package.
gem update --system is a good starting point for making sure you're at the highest version of Rubygems. If your version doesn't support it then you'll need to bootstrap it, because that capability hasn't always been available.
Personally, I never use the repos for my Ruby/Python/Perl installations, instead I make sure I have the needed dependencies, then compile from source.
Consider installing rbenv or RVM and let it manage your Ruby installations. RVM has more features and is more intrusive. rbenv is simpler with fewer features -- personally I use rbenv.