Трябва да инсталирате своя пакет за дистрибуция ruby-dev (или devel), в противен случай няма да можете да създавате разширения за ruby C.
Не съм в ubuntu, но вашата команда за управление на пакети може да е нещо като това:
$ sudo apt-get install ruby-dev build-essential