Du måste installera ditt distro ruby-dev (eller devel)-paket annars kommer du inte att kunna bygga några ruby C-tillägg.
Jag är inte på ubuntu, men ditt pakethanterarkommando kan vara ungefär så här:
$ sudo apt-get install ruby-dev build-essential