If I was connecting anything else coil-based (like a relay) to an Arduino, I'd stick a diode across the coil facing the other way, so when the coil's power goes off and the magnetic field collapses, any voltage it generates can dissipate through the diode rather than zapping my Arduino. That approach won't work with my stepper, as the voltage across the coil could be in either direction depending on which step the motor's at.
DISCLAIMER - I haven't completely thought this through, or analyzed the circuit and current flow.
You can reverse the coil connection, but from the Arduino's point-of-view, you cannot reverse the output polarity and put-out a negative voltage. So, I think a "regular" diode (silicon or schottky) to ground on each Arduino output will protect it from negative spikes, and another diode to +5V will protect it from positive spikes over 5V.