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.