Get a four AA cell holder with four AA cells.
Connect the black wire to your Arduino's ground, and the red wire to the servo supply wires.
Do not use 9V batteries, unless you're powering a smoke alarm.
Do not use two 9V batteries unless you're powering two smoke alarms.