I think capacitors with a blocking diode would be the right call. How long does it need to supply power to the Arduino for? And are you running anything else off of this, or only the Arduino?
Basically, knowing how much power draw (current) that you need, and how long you need it for, and then also how much of a voltage droop is acceptable will tell you how big the capacitors need to be. I'm going to use a bunch of round numbers for easy math, but hopefully you can see how to adapt for your project.
Let's say you're at 5V, and you're drawing 100mA (a lot for just an Arduino, but not so much if you're also running LEDs and a radio, or a servo, or whatever).
If the voltage droop from the batteries due to the motors spinning up lasts for 1 second, then we just need to calculate how much charge that is, and how big the capacitor needs to be to keep it within a certain range.
The total charge, in Coulombs, is 100mA x 1 second = 100mC.
The voltage on a capacitor is: V = charge (in Coulombs) / capacitance (in Farads)
So say you want the voltage drop on the capacitor to be less than 0.5V. Then that's 10% of the initial voltage, so 10x on the capacitor (1/10%) gives you the ballpark. Which means 1F capacitor should be the ballpark you need.
Of course there's simplifications here. (And it's been a while since I did this formally - hopefully I didn't make any big mistakes.) Also real capacitors will not act the same as an ideal one, and tolerances on capacitors are HUGE. Of course the real voltage drop is an exponential, and the current draw will also have part that changes with voltage, but not the same as a resistor, so it would take a bunch of math to calculate exactly.
However, if you can get a ballpark answer and then double it or so, for tolerances, you'll probably be good enough. Heck, for a hobby level project maybe simply going 10x for a few pennies more would be a good idea.