GCC, as well as the normal development libraries and header files need to be included. On Ubuntu, this means installing the build-essential package. This will include make, gcc, etc and Ruby will be all set to build.
$ sudo apt-get install build-essential
