`require': no such file to load -- mkmf (LoadError)

After some search for a solution it turns out the -dev package is needed, not just ruby1.8. So if you have ruby1.9.1 doing

sudo apt-get install ruby1.9.1-dev

or to install generic ruby version, use (as per @lamplightdev comment):

sudo apt-get install ruby-dev

should fix it.

Try locate mkmf to see if the file is actually there.

This is the answer that worked for me. Was in the comments above, but deserves its rightful place as answer for ubuntu 12.04 ruby 1.8.7

sudo apt-get install ruby-dev
# if above doesnt work make sure you have build essential
sudo apt-get install build-essential