Do you specifically need (or want) to use a 9V battery? They are not good choices for anything under a lot of load, such as motors. They do not store that much charge, and thus will die very quickly. Regardless of what you do, ensure that you have decoupling capacitors at the power pin of every IC in use, and you have a couple of bulk caps at the power feed for the motors to help with the immediate draw. Sometimes, a motor turning on can drop the line voltage enough that the other circuitry will reset. This is, of course, undesirable!
Option 1 - Dual Battery Banks
You could use two battery banks: 9V for your circuitry, and 3V (2 x 1.5V alkaline or 3 x 1.2V rechargeable batteries). If using the rechargeable batteries, note that 3 of them in series will produce at least 3.6V, so you should use a maximum duty of 80% in a PWM speed controller, so the maximum average voltage is around 3V.
Using two battery banks is rather common in robotics, but not ideal since you have two different charge levels to worry about. For things to work smoothly, the ground terminals of the two batteries (and any power components) should be shared.
Option 2 - Regulating the Voltage for the Motors
The most common thing to do in this situation would be to regulate the 9V down to 3V for use with the motors. This can be done with a linear regulator, but it would be very inefficient since most of the power would be wasted:
Wasted Power = (V_Source - V_Motor) * (I_Motor(s) + I_Regulator)
Using a switching regulator is a better choice, but it is still going to waste at least 10% of the battery power.
Option 3 - Boost the Voltage for the circuitry
I would recommend using a smaller power source suitable for the motors (around 3V DC) and then boosting that voltage level up with a switching regulator to power the Arduino and any other circuitry. A lot less power will be wasted because the circuitry will be drawing a lot less current than the motors.
On top of that, the circuitry itself may be able to run from a lower voltage source, such as 3V DC. The Arduino has an on board voltage regulator to create a stable 5V level for the microcontroller and other parts, but the AVR chip will work fine at 3V DC if you bypass the on board regulator. I don't know what other components are on the Arduino board or what other circuitry / sensors you plan to use that might actually need that 5V to work.
Edit: I neglected the fact that this AVR based Arduino board is using an external 16MHz crystal which does require the higher voltage (5V) to operate. The AVR chip will only operate up to 10MHz with less than 4.5V.
Option 4 - Use 5V Motors
If you were to get different motors that operated at a higher voltage, you could use a 5V (or 4.8V) battery pack. With this, you could bypass the voltage regulator on the Arduino board, as I mentioned at the end of Option 3. In all actuality, the 3V motors might be OK at this voltage anyway, just so long as you do not exceed a PWM duty of 60% when driving them.