I bought a robot package for my arduino UNO that has four 5V DC Motors. The Arduino cannot handle more than one motor at full speed. Adding additional motors just decreases the speed or rotation. Is it possible to just buy batteries with a higher mAh rating or do I need to buy a motor shield?
EDIT:
I have a 9V battery power supply or a 6V (4 AA Duras) availible. The 9V battery would plug into the board's normal power plug and the AAs connect through VIN.
Use an h bridge it can drive 4 motors in one direction or 2 bi-directionaly. Also lets you use as much voltage as you want (up to the chips limit). Check ebay there dirt cheap.
Just to clarify... you're providing the power to the motors from the Arduino? I'm surprised it can handle even one....
Far better to use a controller board with an h-bridge as Ogmudbones says, but it needn't necessarily be a shield (a shield being a module that plugs on top of the Arduino) but can be standalone. I use one of these to drive 2 motors; see here to look at what else Pololu has on offer.
You'll need to find out what current your motors draw, and allow for the worst case which is the stall current.