You have stiffened the paper by greatly increasing its bending moment of intertia. This can occur in at least two ways:
1.) When you unfolded the paper, it still had some residual bend which made the paper form a very shallow 'V'. Even though shallow. it is much deeper than the thickness of the original paper.
2.) When you unfolded the paper, it still had some residual bend which made the paper form a very shallow 'V' which was very localized to the area next to the bend. Even if you refold the paper in the opposite way, to take out or minimize the original fold, there is still a shallow 'V'. Even though it might be much shallower than in case 1, it is much deeper than the thickness of the original paper.
In both cases, the increased resistance to bending comes from the new geometry of the paper, more specifially, the geometry of a cross-section of the paper which goes through the bend.
Think of the unbent paper as a beam. Its resistance to bending is proportional to b(d^3), where 'b' is the width of the beam and 'd' is the depth. If you take a piece of 8.5" x 11" piece of paper and lay it flat over a pencil on the table, the paper will flop so that both ends touch the table. The paper forms a beam: 'b' is 8.5" or 11" (depending on how you laid the paper) and 'd' is the thickness of the sheet (say, about one one-hundreth of an inch).
How to improve the stiffness and strength of this beam? Fold the paper, accordion-style, with sharp 1/2" folds. Then lay it across the pencil, so that the folds are perdendicular to the pencil.
Assume that you folded the paper into an accordion that was 1.1" wide (one tenth of the original unfolded 11"), had about 22 folds and was 8.5" long. The 'b' for this new beam is 0.5", which is 50 times more than the (1/100) of an inch thickness of the paper. The new beam is (50)(50)(50)/10 = 12500 times stiffer than the unfolded sheet.
Now, let's go back to your sheet with the one bend. When you folded that sheet, you increased 'd'. The amount is hard to quantify, but I would ballpark it at a factor of 5, even if you tried to straighten out the bend by refolding it the opposite way. Again, guesstimate that 'b' of the localized area affected by the bend is 1/10 of the original sheet width. So the new resistance to bending increased by a factor of (5)(5)(5)/10 = 12.5 times the unfolded sheet.
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.
Best Answer
I remember that the question in your title was busted in Mythbusters episode 72. A simple google search also gives many other examples.
As for single- vs alternate-direction folding, I'm guessing that the latter would allow for more folds. It is the thickness vs length along a fold that basically tells you if a fold is possible, since there is always going to be a curvature to the fold. Alternate-direction folding uses both flat directions of the paper, so you run out of length slightly slower. This would be a small effect since you have the linear decrease in length vs the exponential increase in thickness.
Thanks to gerry for the key word (given in a comment above). I can now make my above guess more concrete. The limit on the number of folds (for a given length) does follow from the necessary curvature on the fold. The type of image you see for this makes it clear what's going on
For a piece of paper with thickness $t$, the length $L$ needed to make $n$ folds is (OEIS) $$ L/t = \frac{\pi}6 (2^n+4)(2^n-1) \,.$$ This formula was originally derived by (the then Junior high school student) Britney Gallivan in 2001. I find it amazing that it was not known before that time... (and full credit to Britney). For alternate folding of a square piece of paper, the corresponding formula is $$ L/t = \pi 2^{3(n-1)/2} \,.$$
Both formulae give $L=t\,\pi$ as the minimum length required for a single fold. This is because, assuming the paper does not stretch and the inside of the fold is perfectly flat, a single fold uses up the length of a semicircle with outside diameter equal to the thickness of the paper. So if $L < t\,\pi$ then you don't have enough paper to go around the fold.
Let's ignore a lot of the subtleties of the linear folding problem and say that each time you fold the paper you halve its length and double its thickness: $ L_i = \tfrac12 L_{i-1} = 2^{-i}L_0 $ and $ t_i = 2 t_{i-1} = 2^{i} t_0 $, where $L=L_0$ and $t=t_0$ are the original length and thickness respectively. On the final fold (to make it n folds) you need $L_{n-1} \leq \pi t_{n-1}$ which implies $L \leq \frac14\pi\,2^{2n} t$. Qualitatively this reproduce the linear folding result given above. The difference comes from the fact you lose slightly over half of the length on each fold.
These formulae can be inverted and plotted to give the logarithmic graphs
where $L$ is measured in units of $t$. The linear folding is shown in red and the alternate direction folding is given in blue. The boxed area is shown in the inset graphic and details the point where alternate folding permanently gains an extra fold over linear folding.
You can see that there exist certain length ranges where you get more folds with alternate than linear folding. After $L/t = 64\pi \approx 201$ you always get one or more extra folds with alternate compared to linear. You can find similar numbers for two or more extra folds, etc...
Looking back on this answer, I really think that I should ditch my theorist tendencies and put some approximate numbers in here. Let's assume that the 8 alternating fold limit for a "normal" piece of paper is correct. Normal office paper is approximately 0.1mm thick. This means that a normal piece of paper must be $$ L \approx \pi\,(0.1\text{mm}) 2^{3\times 7/2} \approx 0.3 \times 2^{10.5}\,\text{mm} \approx .3 \times 1000 \, \text{mm} = 300 \text{mm} \,. $$ Luckily this matches the normal size of office paper, e.g. A4 is 210mm * 297mm.
The last range where you get the same number of folds for linear and alternate folding is $L/t \in (50\pi,64\pi) \approx (157,201)$, where both methods yield 4 folds. For a square piece of paper 0.1mm thick, this corresponds to 15cm and 20cm squares respectively. With less giving only three folds for linear and more giving five folds for alternating. Some simple experiments show that this is approximately correct.