Powering a Futaba S3003 servo
I'm going to do a bit of math on this and make some outlandish assumptions because the data sheet does not give enough information. Stall torque is reckoned to be about ~3.5 kg.cm and full speed is reckoned to be about ~0.2 seconds per 60 degrees of rotation.

Many thanks to Brian Drummond for correcting my stupid math mistake so here's the corrected answer with a bit more theory. First, it is a fair assumption that the servo will contain a small dc motor and, generally, this is the torque-speed characteristic for such a motor: -



Note the blue line - at zero speed, torque is maximum (stall torque) and with no load (zero mechanical torque other than losses in the bearings), speed is maximum. This is just a graph of any old motor I stole from the internet BUT it is largely representative of all DC motors.

Now look at the red curve - this is mechanical power out and equates to: -

Mechanical power = \$2\pi n T\$ where n is revs per second and T is torque in newton metres (N.m)

So, the 3.5 kg.cm translates to approximately 35 N.cm or about 0.35 N.m 

A "speed" of 0.2 seconds per 60 degrees is upside down but, rearranging, it basically means 0.166 revs per fifth of a second and this translates to 0.833 revs per second.

Go back to the graph and note that max power is roughly when both torque and speed are at their respective half values therefore,

Power is \$2 \times\pi \times (0.833/2) \times (0.35/2)\$ = 0.458 watts

This is the peak mechanical output power I have estimated from the limited information in the data sheet. Of course it might be a bit higher or lower. 

Next, a motor this small may not be very efficient at converting electrical power to mechancial power so we need to apply a "frig" factor. Let's say it's 50% efficient. This now means the input electical power might be about 0.9 watts.

There is a lot of hand waving here and to play a little more safely you might assume that the power supply needs to supply maybe double this value. I suspect there will be a little H bridge controller inside the servo and this might only be 50% efficient so maybe 2 watts should cover most eventualities.

Please insert your own numbers and frig factors into the equations if you think I may have over-egged the omelette.