I think that it totally depends on how the marketing types are applying the word. It may mean something totally different to the engineer that designed the UPS. I would send your question to the technical support for the unit (or just a general question to all of the various UPS manufacturers: APC, Belkin, Tripp-Lite, etc.
As for my perceptions, it would depend on how it is implemented. Taking Automatic voltage regulation at its face value would imply that the voltage is maintained at a certain level when the input voltage doesn't meet the specification. But what the range of that specification before it maintains that voltage is open to question. Does it start regulating at 108V as mentioned here? Or less? Or more?
Power conditioning, in my understanding, is probably a step up from AVR. It constantly regulates and cleans power (removes very small spikes, line noise, harmonics, etc). You can buy power conditioners that have absolutely no ability to supply battery backup capability, they just clean the power. But often what many products do is what Looney said: incoming power charges the battery and then the battery ALWAYS supplies power to the computer. This completely isolates the line voltage from the components hooked up to the PSU.
Interstingly (well, I think it is interesting) this is what the definition of UN-interruptible power supply used to be: the power was regulated constantly, hence UN-interruptible. But anymore the UPS has also come to encompass power supplies that only come on when the power goes out: i.e. they are interrupted *UNLESS* the power goes out.
Here is a link about power conditioning:
http://www.dansdata.com/sbs9.htm
(I just did a quick Google search; do one of your own for "power condintioner" or whatever else to find MANY more sources.)
Another term you might see is Line Interactive UPS: this just might be another term for AVR or power conditioning depending on the company or marketing department. This tends to be a step up from a basic battery backup device which only comes on if the power goes out totally. Line interactive "interacts" with the line voltage. Imagine that!