Musisz zainstalować swoją dystrybucję ruby-dev (lub devel), inaczej nie będziesz w stanie zbudować żadnych rozszerzeń ruby C.
Nie jestem na ubuntu, ale polecenie menedżera pakietów może wyglądać mniej więcej tak:
$ sudo apt-get install ruby-dev build-essential
