If your stepper motor is running at 9v 0.5A, you may be able to run the whole thing on a 9v-1A supply like this one: http://www.adafruit.com/products/63
The easiest way is to plug the power supply connector into the Arduino and install the power jumper on the shield. This will connect the motor supply to the Arduino VIN.
Stepper motors typically don't cause as many power-supply problems as DC motors. But if you experience erratic operation, you you may need to go to separate supplies.