Rails installation failed on Ubuntu with “cannot load such file — mkmf”

mkmf is part of the ruby-dev package if I’m not mistaken. Try:

sudo aptitude install ruby1.9.1-dev

Of course you may be better off installing ruby through RVM 🙂