mkmf
is part of the ruby1.9.1-dev
package. This package contains the header files needed for extension libraries for Ruby 1.9.1. You need to install the ruby1.9.1-dev
package by doing:
sudo apt-get install ruby1.9.1-dev
Then you can install Rails as per normal.
Generally it's easier to just do:
sudo apt-get install ruby-dev