Every robot needs some form of energy to come 'alive', therefore it is only natural to start with delivering energy using a common household battery. One of the first things to do when designing your robot's power supply is to take stock of the various current and voltage requirements of your subsystems and components. For the starter kit we need to supply power to the ATMega328 and the various sensors and LEDs.
From the ATMega328 datasheet we see that we need to supply it with a steady voltage of 1.8 - 5.5 volts and a maximum power of 200mA which depends on what we are doing with the chips outputs.
Since we will not be doing all the above at one time we easily fit under the 0.5 Amp power requirement. For cheapness, simplicity and packaging the 5 volt linear regulator 7805 was chosen. Note we will not be supplying the test motor through the regulator.
The downside to using the 7805 is the need to stay above 7 volts to ensure proper regulation. Often referred to as having a dropout voltage of 2 volts. Therefore the choice was made to use a 9 Volt battery.
Rules of Thumb:
It is usually good enough to have a single battery pack to drive your electronics and motors, if and only if, the current draw is under 1 Amp and you take precautions such as isolating capacitors/diodes.
If your current requirements are greater than 1 Amp then you should look to using separate power supplies. One for driving your electronics and one for the motors. Just connect the two supplies to a common ground.
A good next project is to use a DC-DC converter such as the MAX631, which will allow you to use smaller voltages from something like a couple AA batteries to give a regulated 5 volts.