How to Install Ruby gems on all agents using TeamCity?
Take a look at Bundler.
You could maintain a list of your required gems in a Gemfile, then run bundle install on each machine before the build starts. This would install all of the gems in the Gemfile (and you could lock gems to a particular version by also including the Gemfile.lock file).