Du skal installere din distro ruby-dev (eller devel)-pakke, ellers vil du ikke være i stand til at bygge nogen ruby C-udvidelser.
Jeg er ikke på ubuntu, men din pakke-manager-kommando kan se nogenlunde sådan ud:
$ sudo apt-get install ruby-dev build-essential