Echo195: A "Deep Cycle" battery is designed to be repeatedly discharged below 50% charge. Your average starting battery (what's in most vehicles) is not designed to be discharged much below 80% charge.
The battery you are asking about is usually refered to as a deep cycle marine battery because they are typically used on boats. You can find them at wal-mart for about the same price as a car battery. The bigger the better. A 12 volt solar panel would go with that battery nicely.