Em toda a versão atualmente suportada do Ubuntu (incluindo o Ubuntu 14.04), abra o terminal e digite:
sudo apt-get install ruby-dev
Este pacote contém os arquivos de cabeçalho e a biblioteca mkmf, necessários para criar uma biblioteca de extensões para o Ruby. Também é necessário construir muitas gemas.
Fonte: link