I've found that using a regular automobile battery, (84 amp-hour), does well when power outages don't last more than a couple of days. YMMV.
Deep-cycle batteries, though, can be found at most marine supply stores.

Car batteries are optimized to provide the high current needed to operate the starter in a car.
The cold craning amps are delivered for only about 30 seconds before giving the battery a chance to recover.

Deep cycle batteries are designed to deliver rated amp-hours at lower discharge rates, and not short out the plates as the enlarge from discharging.

The Optima AGM batteries are available in deep cycle and are well thought of... http://www.optimabatteries.com/optima_products/yellowtop/index.php

Thank you all!