My four-year-old daughter asked me why paper tends to fall apart when wet, and I wasn't sure. I speculated that the water lubricates the paper fibers so that they can untangle and separate more easily, but I really wasn't sure.
Forever_a_Newcomer is on the right lines, but it's not like water dissolving salt.
Paper is mostly made from cellulose fibres (depending on the type there may also be filers and glazes like clay). Cellulose molecules bristle with hydroxyl (OH) groups, and these form hydrogen bonds with each other. It's these hydrogen bonds that make the individual fibres stiff, and also hold the fibres together.
Water is also full of OH bonds, obviously since it's H$_2$O, and the water molecules form hydrogen bonds with the hydroxyl groups on the cellulose, which breaks the hydrogen bonds that cellulose molecules form with each other. There are two results from this: firstly the cellulose fibes in the paper become floppy, because their internal hydrogen bonds are broken, and secondly the fibres separate from each other more easily. The combination of these two effects makes paper easier to tear apart when wet.
Most organic materials show similar behaviour. For example cotton is also easier to tear when wet (cotton is also made mostly from cellulose). Also hair becomes floppier and more easily damaged when wet, though the effect is less pronounced because hair contains fewer hydrogen bonds than cellulose fibres.
You are close to mark, it's a kind lubrication.
Cohesive force between the cellulose fibers is of electrostatic origin. As water molecules, which are small dipoles, penetrate between the fibers they align with electric field. This effectively shields them of each other, greatly diminishing the force. Thus the easy untangling of the fibers (what we see as ripping).
It's similar to how water dissolves salt, here's an animation for your Daughter: http://www.youtube.com/watch?v=xdedxfhcpWo