Make sure you have the proper library files before doing this (i.e. on Ubuntu its zlib1g-dev, installed via apt-get)
apt-get zlib1g-dev cd /usr/local/src/ruby-1.8.6/ext/zlib ruby extconf.rb --with-zlib-include=/usr/include --with-zlib-lib=/usr/lib make make install
The 'make' command should have all output lines NOT '...no'
If it does, then zlib1g-dev is NOT installed. Get it via the packages and redo this to create the makefile
After this return to the rubygems source directory and run:
ruby setup.rb