Problem: You're trying to install a gem and you encounter an error reading no such file to load -- mkmf. This doesn't always occur, only when you're trying to install gems with native C code that must be compiled.
Solution: Install your operating system's development environment. Most operating systems don't come with a C compiler and related build tools. In order to compile gems with native C extensions, you'll need these. How to install these depends on your operating system.
On Ubuntu Linux, there are a few packages you need to install with apt. Once these are installed, this error should be fixed.
$ sudo apt-get install build-essential libopenssl-ruby ruby1.8-dev
For other distributions of Linux, refer to your distributions documentation.
On Mac OS X 10.6 "Snow Leopard" (and possibly earlier or later versions), simply install XCode. Specific directions on how to do this, complete with screenshots, are available here.
Windows is the least friendly operating system to work with in this respect. In the past, this was a very difficult thing to get working. However, Ruby Installer provides a DevKit that may work for you.