Should I ground the Arduino to the batteries?
That question in particular makes me go hmm. Are you using multiple power sources (batteries, power supplies, whatever)? If so, you have to make sure you have a common ground for everything to work properly together. On the flip side, you don't want to get carried away with tying all sorts of grounds together or you could create a ground loop that will also be a source of noise.
If you're using two batteries, tie their grounds together, then send this common ground to each device that needs power, and of course tie the positive of the appropriate battery to each device as well. One battery will power the Sabertooth motor controller, and the other will power the Arduino and encoder. Do not tie grounds together between devices though.