Am I able to plug into my arduino a battery that is rated higher than 5 volts?
I mean, Ive seen arduinos with a 9-volt battery hanging off of them before, but what I have in mind is actually a cordless drill battery.
A cordless drill battery would be sufficient enough to power the arduino and drive a solenoid I am wanting to use.
How can I make my arduino be powered by a large battery (16v) without frying the board? Can I just plug it in and not worry about it?
Google: arduino power supply
First hit: http://www.arduino.cc/en/Main/Howto
At 4.
"(...), power the board with an external power supply (6 to 25 volts DC, with the core of the connector positive)."
So, in theory, I could just wire in a car battery to the arduino and everything would still be fine?
Something just doesnt seem right....
The car battery would last a long time running an Arduino. 
Theres a voltage regulator on the Arduino that reduces whatever you feed into the DC socket to 5v for the board to run on. The extra voltage is dissipated as heat and if you use too much current and/or too much voltage the voltage regulator will get hot, if it gets to warm it shuts off an the arduino will reset. It would be fine just running a bare Arduino from a 12V car battery.
Theoretically you can have up to 20V going into the arduino Duemilanove. The then the built in voltage regulator starts heating up really bad and there can be some damage. So its best to keep it inside the 6 to 12 volt range. The voltage regulator can handle 12V of input with no problem. But if the overal load of you design is too much you can always use separate power sources. so long as your not imputing more then 5V into any pins.
Yeah if you need a high voltage (20v or so) powering your arduino then you want to use a transformer or strap a big heatsink to your regulator.
Mowcius
or different stages of regulators ie 24v > 12 > 5