Battery voltage sags when you draw more current than the battery can generate.
As long as the "sagged" voltage is still over the 5V + dropout value of the Arduino regulator, the Arduino won't see the voltage drop.
It may, however, see voltage spikes, depending on how good the filtering is in the regulator. Adding more capacitors before or after the regulator may help, as may spike/transient suppression diodes.
As everyone else has said, the 9V battery is puny. If you have two motors, they will easily draw 1A if you suddenly reverse direction on both at once. The 9V battery will croak, and the Arduino likely reset. (If you have two batteries with common ground, then the Arduino wouldn't be affected.)
I like to use a bench power supply while developing (saves on batteries :-) and then use LiPo when un-tethered. You can use a UBEC (which is a switching power converter for use on RC planes etc) to get 6V or 5V out of a 7.4V or 11.1V LiPo battery. If you output 5V, you may even pipe that straight into the 5V of the Arduino, instead of taking the losses from the linear regulator. This probably requires additional filtering, though -- both at the motor driver end, and on the output from the UBEC. You could also use a 6V UBEC and put that into the Vin of the Arduino, to reduce losses, and use the 6V to power the motors. Note that motors are very voltage forgiving, as long as you don't run them too hot. If you use PWM to control the motors, then you can use significantly higher voltage than the "rated" voltage for the motor. Same thing if you use a current controlling motor controller, and make sure to not exceed rated current of the motors. You can even use a 7.2V UBEC and a 11.1V LiPo battery for this.
One thing I don't like about the Arduino regulators: They are not ULDO. There exists parts that only need 0.3V over the regulated voltage (LF50ABV for example) as opposed to the 1.2 - 2.0V typically used by "normal" regulators. This translates to lower losses, and better ability to run on lower voltages. The Arduino is marginal on 6.0V in -- it really wants 6.5V in for a stable 5.0V out.
You can use an UBEC like this: http://www.hobbypartz.com/ub2liin.html
Or a DC DC converter like this: http://www.pololu.com/catalog/product/2110
With that, you can use a rechargeable LiPo battery like this: http://www.hobbypartz.com/83p-950mah-3s1p-111-15c.html
or like this: http://www.hobbyking.com/hobbyking/store/uh_viewItem.asp?idProduct=16772