As you say, paper is made from a network of cellulose fibres (typically derived from wood these days). The fibres are secured to each other partly by hydrogen bonds but also by binders added to the wood pulp, and in both cases the strength of the binds is reduced by water.
The mechanical properties of the paper are determined by the size and shape of the cellulose fibres and also by the way the fibres are arranged i.e. how they link with each other to form a network. During the manufacture of the paper the manufacturer will go to great lengths to try and optimise the arrangement of the cellulose fibres to give the required strength to the paper.
The problem is that the fibres would really like to be aligned with each other because this maximises the contact area and therefore maximises the bonding energy between the fibres. But this arrangement drastically weakens the paper because the aligned fibres are now easily fractured in a direction parallel to the alignment. This is a problem because when you wet the paper the breaking of the hydrogen bonds and softening of the binder allows the fibres to become more mobile, though not completely mobile, and the fibres can rearrange to some extent. Hence when the wet paper has dried the microstructure will have changed compared to the paper before it was wetted.
Exactly how much the microstructure will change, and how those changes will affect the mechanical properties, depends on lots of factors and it's hard to make any general rules. However, bearing in mind that the original structure was optimised for mechanical properties, any change is likely to result in a sub-optimal structure i.e. the paper will have changed for the worse.