Thanks for the info, CrossRoads. It is indeed the standard smoke detector-type square 9V battery. I looked up the info on Wikipedia; a standard AA battery supplies something around 400 to 900 mAh, whereas the one 9V only has 565 mAh (according to Wikipedia). So as you said, putting three together gives me (~400*3) mAh which is plenty more power than the 9V. Does my logic sound right? If so, I guess it's back to Radio Shack to see if they have something like that!

One question though, should I be using Vin or 5V when running on external power on the Uno? The docs seem to suggest Vin is the way to go.
It depends on how your batteries are wired.
I'm still rather new to electronics myself but this is how I understand it:
In series, the voltage is cumulative but the capacity amount is not. In parallel the capacity is cumulative but the voltage is not. Think of it this way, in series (the most common way batteries are used) all 3 of the AA batteries will be drawn upon at the same time. But in parallel it's more like only one battery is being drawn on at the a time. So 3 AAs (1.5v each) will need to be wired in series to provide 4.5v to your arduino giving it enough power to operate normally. If you wired them in parallel you'd only get 1.5v of power to the arduino board, which is not enough to power the board. Wiring batteries in series is wiring them negative to positive with the end positive and negatives being your leads. Most battery holders that you will find at radioshack are done in this fashion, that is why in a 3 battery holder, one will go in the opposite direction of the other two.
Really I would think your 9v would be enough to power the circuit unless the 9v is already depleted a good bit. But it could also be something to do with the batteries maximum discharge rate. Some batteries can discharge faster than others, and your entire circuit cannot draw more than the batteries maximum discharge rate or you will see power problems even if you have sufficient voltage. The mAh ratings you are referring to is the total capacity of the battery.
This is how the capacity would work, lets say your circuit is drawing 150 mA. Assuming your batteries are capable of discharging at least 150 mA rate, and it has a capacity of 600 mAh, you should be able to run your circuit for 4 hours (600 mAh/ 150mA basic algebra mA cancels out on top and bottom and you are left with hours) before the battery is dead (give or take a little depending on temperature and some other variables).
Again, I'm still learning, but that is my understanding. If any of it wrong someone please correct me!