This is just to remind myself so I don't waste time looking into it next time I run into the same problem:
If you're installing a gem and you see...
"extconf.rb:1:in `require': no such file to load -- mkmf (LoadError)"
...it means you didn't install the ruby1.8-dev package.