Hello, all
I tried to power Arduino (Duemilianove) and servos/motors it controlled with the same battery, but Arduino continuously restarted during the operation. Actually it was a surprise for me, since Arduino already has voltage regulator chip and filtering capacitors in the input circuits...
I solve this problem by supplying them with different batteries, but I don't like this solution. Could anyone help - how to provide single power supply?
Depends on whether the Arduino reset is being caused by voltage fluxuation or noise spikes.
Fluxuation means you need a bigger battery, as in use D cells instead of AA cells.
Noise spikes means that your filtering is in the wrong place. The motors themselves need to have 0.1 or 0.01 uF capacitors. These can either be a single capacitor across the motor terminals, or two capacitors, each one between a motor terminal and the metal case on the motor. This suppresses commutator hash from the brushes.
Also, when the current is cut to any coil, and a motor is a collection of coils, the magnetic field collapse generates a reverse voltage pulse that can be pretty severe. Diodes are commonly used on relays to suppress this inductive kick. Using the diode will only work if you aren't reversing polarity on the motor. This page has a little more information about solenoids and inductive kick: Arduino Playground - SolenoidTutorial
The easiest way is as you've found, two separate supplies.
PS: on trying the single battery, were you using power tapped off the Arduino to power servos and motors, or did each item's power input go to the positive supplies terminal?
I suggest separate supplies/batteries, as the "constant reset" problem suggests the voltage of the battery is dipping low enough (temporarily) to go below the voltage regulator's dropout value.
If it's this bad, capacitors are probably not going to fix it. Motors & digital electronics are happiest when they are separate.
I would say this is a classic case of lack of decoupling see :-
http://www.thebox.myzen.co.uk/Tutorial/De-coupling.html
Remember just because you have some decoupling don't mean you have enough.
I found that decoupling worked for me in this scenario. Also, I found that there wasn't enough current when using USB to power the Arduino and the motors. And this also resulted in a reset.
After decoupling and using separate power/gnd pins for the motors and the motor driver, I found that I could run from USB, if at low speed, or run perfectly at full speed off a 1100mAh LiPo battery.
Mind, I didn't do the decoupling calculations perfectly, and rather tried a few different scenarios out until one worked for me.
Good link there Grumpy Mike. One thing I learned messing with RF circuits, bypass every stage's power input to ground with the appropriate capacitor. You want your DC to be DC. Actually, I'm working on a WWVB receiver clock at the moment, and the cause of a portion of the problems people have is that the receiver board hasn't had any capacitors placed across its voltage inputs to filter out noise from the microprocessor.
I think a key improvement would result if the motor circuit used it's own low impeance ground and power wiring right to the battery terminals, that should help some with 'ground bounce'. The Arduino can then have it's own dedicated non-shared ground and power wiring to the battery. Keeping motor current draw off the Arduino pins has got to help the situation. That would be a version of 'star grounding' used in higher power hi-fi and other equipment where every stage or module has it's own power and ground wiring back to a central point, usually the main filter capacitors connections from the main DC power supply. Decoupling caps can also help, but their job is made easier if current paths are seperated on different power and ground wires.
Lefty
Like wiring your 100W mobile transceiver directly to the battery to help eliminate all those odd effects when you key to transmit. Especially in the modern processor controlled generation of automobiles. 
It all starts with proper grounding, bonding and power distribution!