I'm sorry if this seems difficult, but then its not a simple question for others to answer without a little bit more from you since many of the sub-questions involved can only really be answered by you.
I'm not sure what is typically used, I use rechargeable AA nimh cells, but that is what I have around.
If you want this to come out well you are going to need to do some research and some arithmetic. I can lay down the process I would go through for something like this.
First ask, what do I want my robot to do? You want yours to be able to wander without running into obstacles directly in front of it. Then I would try to break it down to sub-problems, the above goal seems to have two in my mind, movement and obstacle detection.
OK, then how fast should it be able to move? For how long? These are questions that you can answer. Then pick motors and gears based on that and projected weight of the finished bot. Since this is going to be your first robot you probably don't have any firm requirements for speed which makes it easy to pick a motor, those motors with that gearbox should be fine.
How will it detect obstacles? Great, you've picked a method with the ir sensor.
So now you battery will have to provide power for the motors, the arduino, the sensor and any other leds or whatever you want to add for style points. In general your motors are going to be by far the biggest current draw so I would mainly worry about that.
Pololu has a datasheet for the motors in the gearbox, http://www.pololu.com/file/download/fa_130ra.pdf?file_id=0J11
, which tells us that the motors have a stall current of 2.1 A and draw .56 A at max efficiency. So I'd want to allow for both motors running at the same time with some load, and plan to avoid stall conditions and look for a battery that can provide at least about 1.5 A continuous and I would like to be able to run it for, say half an hour (another question only you can answer).
When looking at batteries there are a few important numbers, the voltage obviously, the mAh, and its current capacity. Now the 9V (nominal value, actual value likely to vary between ~10 and ~6 or lower depending on how discharged it is) is a bad choice for several reasons
#1. You have nothing that wants 9V, you will have to regulate this down to 5V for the arduino and the sensor, and those motors only want 3V (you can run them higher, but they will burn out faster and you probably don't need the speed). This leaves the voltage regulator on your arduino dissipating power for no reason, wasted power is bad. I'm not exactly sure how you planned on getting the motors involved, but it wouldn't work well, if at all.
#2. A 9V is generally going to be rated ~550 mAh, or to put it another way it can provide 550 milliamps for 1 hour, or 5.5 milliamps for 100 hours (not quite true but we will get to that). So if you have two motors running at .6 A or so under some load, ignoring the other electronics you need ~1.2 A, all the time. So if you just go by the rating you should get about half an hour of charge out of a 9V.
#3. The more current you try to pull out of a battery continuously, the fewer effective mAh you will get out of a battery. First, I would be surprised if a 9V could actually put out that kind of current (its off of energizer's charts for example), and even if it could that would reduce you battery life even further.
#4. The final reason is that batteries voltage level changes over the charge cycle and 9V manufacturers assume you are going to keep using the battery until the voltage drops to about 5V. The problem is that the voltage regulator on the arduino requires an input voltage of about 7V to operate correctly, so there goes a third of the useful discharge cycle for arduino operation.
If you have read this far, you can see a few things. 9Vs suck and were invented as a dirty trick for newbies to electronics (9V = MORE POWER WEEEEEEE!!!!), if you want a robot that works you have to be willing to do some homework or buy a kit, and that I have way too much time on my hands to type all this up.
As suggestions, use AA's as they are much better at providing more current for longer, they are cheap and you can get rechargeable ones easily. Everything above should help illustrate why you should plan plan plan before you build build build. How disappointed would you be if you got it all together and then found the thing ate through batteries at the rate of 5-6 an hour with sub-par performance due to inadequate power?
I hope this has been mildly helpful and will help to encourage you to look at things a little more closely, otherwise my fear that you won't end up with a robot that performs as expected remains. Or get a kit, there is nothing wrong with that and it is a great way to start out.