The interesting part of the state-of-charge curve on a 12V nominal lead acid battery is between about 10V and 14V or so. What I have done is used a 10V zener diode to shift this voltage range into 0V..4V and fed this straight into the 5V A2D. This gives good accuracy over the interesting range and avoids wasting input range of the A2D on the part of the voltage curve (0V..10V) over which the battery is essentially dead.
You should establish your cut-out point based on the discharge rate -- the voltage you will measure is a function of the current being drawn, the capacity of the battery and the state of charge. 10.5V is good a rule of thumb, but you can calculate a more suitable cut-out level if you know the current draw of your load, the internal resistance and the capacity of the battery. Also, if you want the battery to last a while, you should target a 30% or 50% SOC for cut-off, not 0%. Completely discharging a lead acid battery will shorten its life dramatically.
If the battery capacity is small, it will have a large internal resistance and the voltage rebound when the load is removed might be pretty big. If it were me, I would be looking for the voltage to rebound to the 50% or greater charge level -- maybe 12.2V at open circuit -- before returning loads.
Of course if the battery is on a charge circuit, maybe solar panels, then assessing the SOC is more complicated -- a function of how much current is flowing in via the charger, what voltage it's charging at, what the internal resistance and capacity of the battery is.
For a simple circuit, I would in fact incorporate a timer and not rely on hysteresis to get things right. If the SOC drops to, say 30% and you remove the load, and you know that the solar charger takes X hours to charge the battery, you can have your algorithm look for the voltage to rise to -- say 12.8V -- and stay above this level for X hours, before restoring loads.
EDIT: I was rummaging around looking for details on one of these points and found this: http://www.scubaengineer.com/documents/lead_acid_battery_charging_graphs.pdf
An interesting read.