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.