OK, some speculation here, but I think that the transformation from a dry, stiff sponge to a wet, soft sponge may be similar to the transformation of gelatin from a dry, hard powder to a wet, soft jelly-like material. In the case of gelatin, the addition of water causes gelatin to form an extended 3-dimensional linked polymer network with water molecules trapped in the network, so that the material is mostly water. I once had an experiment in which I used gelatin rings which were 6% gelatin by weight and 94% water, and that resulted in a moderately stiff jelly-like material. If you were to dry this material and remove all of the water, the remaining material would of course have a much smaller volume but would also be much stiffer than the 6% gelatin/94% water material, presumably because all that water served to extend the polymer network greatly and sort of acted as a 'lubricant' against the polymer strands rubbing directly against each other. Anyone who has played with gelatin knows how 'bouncy' and easy to deform it is due to the presence of all that water trapped in the material. With the water removed, however, the gelatin network collapses. If a shearing force is exerted on this dried material there is a lot of resistance to deformation, probably due to the collapsed polymer network resulting in the polymer chains directly rubbing against each other.
I'm not familiar with the structure of sponges, but I would guess that the same idea holds for them: When wetted, water extends the structure of the material and water molecules act as a lubricant between various parts of the extended sponge structure at a microscopic level. When dried, all that water lubricant is removed and the structure collapses, resulting in the parts of the collapsed sponge structure directly rubbing against each other, thus increasing the effective stiffness of the material.