Options for powering a Futaba servo
Based on the link to the specifications, this is a "high speed, high torque" servo. Unfortunately, none of the information includes the maximum or typical current draw, though there are warnings to higher gauge wire than usual and to avoid long leads and Y-splitters. 

These are indications that your power supply should be "beefy", and by the class of servos this is in, I would guess you need a supply capable of supplying 5V at up to 3 amps. 

The "harder" the servo has to work to move, the more current it will draw. This servo wants around 5V, but 4.8V is acceptable from a 2S (2 series) LiPo battery pack. 

4.8V, however, is not quite enough for a 5V Arduino at 16MHz (the standard speed). As long as all the Ground wires are connected together, you could have one battery pack for the Arduino and a 4.8V pack for the servo.

All that said, there are only 2 primary specification points of a power source -- Output Voltage and Max current. You should try to MATCH voltage ratings of a power source to the device being powered, and ensure the device being powered DOES NOT EXCEED the current rating of the power source.