Você precisa instalar seu pacote distro ruby-dev (ou devel) caso contrário você não poderá construir nenhuma extensão C ruby.
Eu não estou no Ubuntu, mas seu comando package-manager pode ser um pouco assim:
$ sudo apt-get install ruby-dev build-essential
