In terms of batteries that you need to add water to: _Most_ (though not all) car batteries use flooded cells, where you have the electrode plates sitting in a solution. If you puncture these cells, the electrolyte will leak.
As Albany Tom mentioned, if you over charge (or simply charge properly) a lead-acid battery, you will electrolyze some water into hydrogen and oxygen. If this hydrogen and oxygen escapes, then some water will be used up, which will need to be added later.
Most modern car batteries are 'maintenance free', in that they include a bit of catalyst that recombines the hydrogen and the oxygen, condensing it out as water. For these, you don't have to add water unless something goes _very_ wrong.
In terms of mass change, the reactions in the battery do not change the chemical elements in the cell, nor do they change the number of electrons in the cell. Instead the reactions just change the arrangements. Electrons don't flow out of a battery during discharge, and into the battery during charge. Instead electrons flow out of one terminal, through the load, and into the other terminal, and the _direction_ determines charge and discharge. This means that the will be no significant mass change during charge or discharge (hmm, well I guess a zinc-air battery would get heavier during discharge).
However the different configurations of elements in the battery have different potential energy levels, and thus _must_ have slightly different masses, by the mass-energy relation. In a chemical battery, the difference would be slight; I estimate that for a car battery the mass difference between discharged and fully charged would be about 0.02 picograms, and if you can feel that weight difference I've got a job for you /ubbthreads/images/graemlins/smile.gif
-Jon