Do what digger said with the external resistor, and try to power your servos with less than 9V, they are supposed to be run at 5-6V. This is a bit of problem for the arduino board, which requires a power supply of >7V.
I tried powering my robot with a 11.1V LiPo pack, but my servos didn't like that at all! So I chose to use 6 AAs. This gave ok results when the batteries were fully charged at 1.4 V per battery, but I can only run the robot till the batteries were half empty, since arduino starts to cut out when the AA battery voltages get to around 1V. I added a 100uF cap to help reduce the low volt problem when the servos demand a burst of current, this made the run time a bit longer when the batteries were low.
-Z-