Cleaning: If you use PBW, one batch of PBW can be reused many many times. This may also be true of other cleaners, but I've only ever used PBW.
Sanitizing: As with PBW, one batch of StarSan can be reused many times. The key with StarSan is to make the batch with the cleanest water possible and then keep it in a sealed container.
Cooling: There are lots of ways to cut water usage during cooling. First, you can capture all the water you use to cool the beer and save it for later use as cleaning water. Second, you can build a recirculating cooler that will use far less water. In a recirculating cooler cold water is pumped through the immersion chiller, back into a bucket full of ice and then back into the immersion chiller.
As others have mentioned, you can also decrease the time it takes to chill your beer by using a whirlpool chiller. Faster chilling = less water.