If you install Ruby on CentOS 4 via yum, you'll get version 1.8.1 which latest versions of Rails and other gems have problems running on. Building latest version of Ruby yourself is a bit more involving than the usual download/configure/make/install dance so my recommendation is to use the version (1.8.5) in the Testing rpm repository.

To enable the Testing rpm repository, switch to /etc/yum.repos.d directory then:

wget http://dev.centos.org/centos/4/CentOS-Testing.repo

Change "enabled=0" to "enabled=1" in the .repo file then install ruby:

yum install ruby ruby-irb

At this point, you should have no trouble installing rubygems and rails.