Se você está tendo um problema como esse ao tentar instalar um gem:

Building native extensions.  This could take a while...
ERROR:  While executing gem ... (Gem::Installer::ExtensionBuildError)
    ERROR: Failed to build gem native extension.

ruby extconf.rb install mechanize
extconf.rb:1:in `require': no such file to load -- mkmf (LoadError)
        from extconf.rb:1

Basta instalar o pacote de desenvolvimento do Ruby:

sudo apt-get install ruby1.8-dev