How can I use relays and deal with reverse polarity with the Arduino?
Your Arduino output ports can't supply the kind of current needed by your motors. Worse, they are not prepared to take the inductive spikes that can be caused by brushed DC motors. 

The solution to both problems is to use either a relay, or an H-bridge (with kickback diodes). Unfortuantely most H-bridges are not optimized for 6V, most prefer 12V or higher. For low currents you might check an LD293D, although it won't do that well at 6V. 

If you use a relay note that you can't connect a relay directly to the Arduino pins. There are plenty of relay boards for Arduino that combine a relay with a transistor and the kickback diode (which is now needed for the relay coil).

Note that it might not be a good idea to use the same power for both the motors and the Arduino. Start with two separate battery sets. If you get everything working you might try combining the batteries, maybe with some spike suppression. If anything goes wrong then you know the likely cause.