You can lookup the gems on rubygems.org. They are supposed to list what version of ruby they are compatible with, but that may not always be kept up to date.
If that doesn't narrow it down, you can check the gem's CHANGELOG file on github.
In the end, you may have to just try a few. There's only a handful of versions in common use, so it's not like you have to try then all.
in my experience ruby 1.9.3 is most widely supported at the time of this writing. Ruby 2.0 and 2.1 would also be good to try. 1.8.7 is pretty old and will likely give you a good bit of trouble, but it was the standard for a long time.