Rails installation failed on Ubuntu with "cannot load such file -- mkmf"

I have this problem while installing Rails on Ubuntu 11:

root@salah:/home/salah/rubygems-1.8.15# sudo gem install mysql

Fetching: mysql-2.8.1.gem (100%)
Building native extensions.  This could take a while...
ERROR:  Error installing mysql:
    ERROR: Failed to build gem native extension.

        /usr/bin/ruby1.9.1 extconf.rb
/usr/local/lib/site_ruby/1.9.1/rubygems/custom_require.rb:36:in `require': cannot load such file -- mkmf (LoadError)
    from /usr/local/lib/site_ruby/1.9.1/rubygems/custom_require.rb:36:in `require'
    from extconf.rb:10:in `<main>'


Gem files will remain installed in /usr/lib/ruby/gems/1.9.1/gems/mysql-2.8.1 for inspection.
Results logged to /usr/lib/ruby/gems/1.9.1/gems/mysql-2.8.1/ext/mysql_api/gem_make.out

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 :)

For ubuntu 13.04, this is what worked for me:

sudo apt-get install ruby-dev