For me it was an issue with bundle (which I thought I had installed). Spoiler alert, I didn't, and this is how I fixed it. I'm on a Mac running OS X Yosemite and my terminal version is Darwin Kernel Version 14.3.0:
cd
gem install bundler
or
cd
sudo gem install bundler
If you get something along the lines of the following error:
ERROR: While executing gem ... (Gem::FilePermissionError)
You don't have write permissions for the /Library/Ruby/Gems/2.0.0 directory.
Finally, change your require line from:
require 'rest-client'
to
require 'rest_client'
Then run your code!