I've experimented with this in the past - I tried using a long-distance Sharp IR distance sensor with a float inside a 3" diameter PVC tube. Despite painting the inside of the tube black and using a blue XPS float, I got basically random signals. Presumably, the tube did not help, but it seemed like a good idea to keep the reflector in one place and to prevent it from getting soiled by the water in our cistern (i.e. it would always float one side up).
One way to limit electrolysis, etc. for exposed wires is to use a AC signal - and it doesn't have to be a sine wave, a alternating square wave will suffice. That way, there is no net gain on one electrode or the other and no bubbles will form on the surface of the sensors (thanks Grumpy_MIke) - he suggests using an inverting H-bridge. Limiting the current would obviously also work by slowing the rate of decay. However, over time the effects of decay and/or surface coatings should become noticeable on the signal.
That said, a long capacitance sensor consisting of a thin PVC pipe with Copper tape mounted on it seems like a fairly inexpensive way to get things done without resorting to expensive sensors and you can use the capsense library to interpret the results. See the following link, as the christmas tree water level sensor is nifty http://hacks.ayars.org/2011/12/christmas-tree-water-level-alert.html
E-Tape is expensive but easy to use if your application requires less than 12" of travel see http://www.adafruit.com/products/464
Here is an example of the inverting H-bridge in action: http://gardenbot.org/howTo/soilMoisture/
A nichrome wire / H bridge has been discussed here before also: http://arduino.cc/forum/index.php?topic=71628.0
A resistive approach is shown here: http://lifeboat.co.nz/arduino-water-level-gauge/