I found this build pack
https://github.com/cyberdelia/heroku-geo-buildpack (via multi-buildpack) that seems to install the GROS, PROJ4 and GDAL libraries in to the Heroku App environment
With these settings in the environment (running 'env' inside a terminal after running 'heroku run bash'):
LIBRARY_PATH=/app/vendor/geos/3.3.8/lib:/app/vendor/gdal/1.10.0/lib:/app/vendor/proj/4.8.0/lib
LD_LIBRARY_PATH=/app/vendor/geos/3.3.8/lib:/app/vendor/gdal/1.10.0/lib:/app/vendor/proj/4.8.0/lib
PROJ4_LIBRARY_PATH=/app/vendor/proj/4.8.0/lib
GDAL_LIBRARY_PATH=/app/vendor/gdal/1.10.0/lib
GEOS_LIBRARY_PATH=/app/vendor/geos/3.3.8/lib
GDAL_DATA=/app/vendor/gdal/1.10.0/share/gdal
CPATH=/app/vendor/geos/3.3.8/include:/app/vendor/gdal/1.10.0/include:/app/vendor/proj/4.8.0/include
However if I fire up a console on heroku, "require 'rgeo'" returns false.