Basically, water softeners contain a filter with a chemical that attracts positive ions (like the alkali metals calcium and magnesium). The filter is originally "charged" with sodium ions using the salt you put in the bin. Run hard water through it, and the calcium and magnesium compounds (mostly carbonates) are converted to sodium carbonate, which doesn't cause scaling. The magnesium and calcium remain in the filter media.
Regularly, the filter must be "recharged", the magnesium and calcium in the filter are flushed out by pumping very salty water through the filter. The sodium from the salt replaces the calcium and magnesium in the filter media, which then bond with the free chlorine and hitch a ride down the drain as relatively harmless chlorides.
This process does require quite a bit of water - up to 25 gallons per recharge is the figure I found. However, you have to ask what's more expensive, flushing a few gallons a day through the filter to keep the sodium and calcium out of your plumbing, or calling a plumber to flush a corrosive and poisonous chemical through your pipes to dissolve the scale, then flushing even more water through the pipes to rinse them out so the water is usable again? Not to mention the extra chemicals you'd use with each load of laundry and dishes to keep your clothes from becoming stiff and your dishes free of spots (some of which contain environmentally-harmful phosphates), and the filters you would need to install on faucets and in fridges to clean your drinking water.
There are different systems for determining when to do this admittedly costly recharge cycle. Most of the cheaper ones do it on a schedule which can be programmed based on average demand; every night, every two nights, depending on how much water you normally use each day. Others can sense the sodium content in the filter media and recharge when the sodium is exhausted. Still others simply measure water usage and "know" that a charged filter can soften X gallons. They all have pros and cons, the main tradeoff being price for water efficiency, but some will also recharge any time it's needed, which may be when you need your water (the softener cannot provide soft water, and sometimes can't provide ANY water, during a recharge).