Building Stair Climbing Robot and have power question

I am building a stair climbing robot for a class that will carry a basket full of rubber stamps to the top of a staircase.  My robot will be loosely based off of this robot --->  I am planning on using an Arduino Duemilanove for the microcontroller.  I am planning on using 5 dc motors to power the four wheels on the ground, and 1 continuously rotating servo to power a wheel rotating at the front of the robot which comes into contact with the stair first and projects the device upwards.  My problem is wondering how to power 4 motors and a servo continuously? I also need to have the front pair of motors and the back pair of motors to rotate in opposite directions initially and then stop and rotate in the same direction.  

What is the best way to go about this?

Sorry I am very new to robotics.