Some "back of the napkin" parameters to think about:
o You probably want more of a deep-cycle battery for this application than a starting battery. Think motive/fork lift/industrial vs auto starting. Marine deep cycle might work.
o Sealed lead-acid batteries would be one choice - compact, commonly used in gate openers, UPSs, mobility scooters.
Lead acid batteries:
o Are only good for so many cycles - think 100's. If your lights are on every day, you might be replacing batteries yearly.
o Have less capacity in cold weather. You'd need to oversize.
o A discharged LA battery will freeze -- a charged battery will not freeze. A battery that has been frozen is very likely a dead battery.
One spot fixture might be 2 90w equivalent LED bulbs @ ~ 20w each = 40w @ 12v = 3.3A. So you'd need 3.3Ah of battery at a 3.3A discharge rate per hour of lights on. Scale by the number of hours a night x cloudy days and add some.
On the charging side, You'd need a solar panel & charge controller that would have enough capacity to charge the battery on an average day. It would need to charge at the appropriate rate for the battery.
I think my biggest concern would be keeping (the potentially discharged) battery from freezing.