Last time I used localtunnel I eventually figured out I needed to run "sudo apt-get install ruby1.9.1-dev" first.
The only caveat is that some gems require compilation of native C extensions, which if you don't regularly compile things on your machine may require you to install lots of extra stuff (especially on the Mac).
It's not a problem for me because Ruby is my bread and butter, so of course I have rvm (or rbenv) installed at all times. But as I user I think it's unacceptable to have to do a manual installation just to run extremely simple programs. It'd be nice if the community were more responsive to fixing the problems faced by the package manager maintainers.
All of the RubyGems developers are volunteers—as are most (if not all) of the various package manager maintainers. The way that Debian broke Ruby in the past (I don't know if it still does, but I have heard reports that it's better)…was unconscionable. (This mostly because Debian tried to treat RubyGems like C-based libraries, which are hard to have multiple usable versions of; RubyGems was based on the idea that you might need multiple usable versions of a package around.)
If you want a strange Python package or a certain version, you're better off on Debian and Ubuntu just installing pythonbrew to keep a compiled python in your home folder.
My original complaint though is that people are using "gem install" as the sole documentation for installing a general purpose command-line tool. I'd rather not even know it's written in Ruby (I just want to install it and use it) - instead, I need deep Ruby knowledge just to get the thing running.
If YOU read the content that was linked, you'd see there is a very long README targeted at people who aren't Ruby developers.