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