The program 'rails' is currently not installed

gem install rails needs to be run as root since /var/lib/gems should be 0644 or something. Therefore, use:

sudo gem install rails