I'd say to Make it big enough to hold this battery:
http://www.trojanbattery.com/product/t-1275/
That is basically the only real 12v true deep cycle flooded battery you can get. Top quality.
but you do not need to go this far. A standard group 27 or group 31 marine/dual purpose battery can be found easily at walmart, and will fit in its place with a few inches above it.
Later on if your electrical needs increase and you get sick of visiting walmart trying to warranty batteries, you could get the T-1275.
But even better would be 6v 2 GC-2 golf cart batteries wired in series for 12v.
The 12v marine batteries are OK, but despite "DEEP CYCLE" being written on their sides in bold letters, their internals more resemble a thin plate starting battery than a true deep cycle battery.
But they are the least expensive and good enough, for most. Especially for A 12v Newb who can so easily murder a battery by overdischarging it regularly, and not recharging it fully often enough.
So plan on fitting a 13 inch long battery, a little over 7 inches wide and at least 10 inches tall, but that extra 2 inches of interior height gives you the option of the T-1275, which is a much more robust battery in deep cycle usage, and has 150AH capacity, where as most group 27 is about 105 to 115Amp hours and group 31 can be as high as 125AH and will last only half as many deep cyclesas the t-1275, all factors being equal. The Trojan GC-2's(t-105) would outcycle either easily, all factors being equal