How often should I re-index?

This is up to you, but it's recommended that you process (re-index) your indices regularly - perhaps every day or hour, given that's the options Heroku provides for cron (which is the ideal way to manage this). It comes down to how volatile your data is.

All you need to do is run the fs:index rake task - there's no need to restart Sphinx and/or rebuild your entire setup (the fs:rebuild task).

If you want your data updated more frequently - as every change is made - then delta indexing is what you'll require. You still need to run a full re-index regularly if you're using these though, otherwise processing your delta indices will get slower and slower.