Sie müssen Ihr Distributionspaket ruby-dev (oder devel) installieren, sonst können Sie keine Ruby-C-Erweiterungen bauen.
Ich bin nicht auf Ubuntu, aber Ihr Paketmanager-Befehl könnte ungefähr so aussehen:
$ sudo apt-get install ruby-dev build-essential
