The usual coating of photographic paper consists of (hardened) gelatin, together with a lot of other chemicals. Unless it has some extra protectional coating as described on this wikipedia image the gelatin is directly exposed to the environment, and if you ever have used gelatin for baking or cooking, it gets a bit sticky when wet, and dissolves completely given enough water and time.

This happens a lot to photos which get a bit humidity: the gelatin starts dissolving slightly, and sticks a bit to a surface. The behaviour is a bit like vine gum: if its not too wet, and you act quickly, you can take of most things that stick to it without causing much damage. Just try it: wash your hands, dry them just so much that they are humid but not dripping wet, and touch an old photo that you don't need anymore. Press your fingers firmly on it, and take it of. Often the photo will already stick at the finger, but you can usually peel it off easily. If you carefully look at the photo, you will see your fingerprint in the gelatin structure of the photo, but the colors are still intact. Often when you have a stack of photos that was lying in a box for a few years, you will have the same effect of slight stickyness when browsing them. This is the beginning of a bad effect and a good reason to not store them like that.

Most likely this is what happened to your photos too, but instead of firm pressing, it was the time and humidity that made them stick together more firmly.

So how to resolve (literally?) this situation? If you were ever so curious as to put some vine gum into the freezer, you will notice that they get really hard, and given the temperature is low enough, will easily break. As D. Lambert pointed out, you can try that with the photos too, and the same will happen: you will break the gelatin layer. Depending on where it breaks, more or less of the color bearing material will be torn of. Usually the weakest point is just at the surface of the gelatin layer, so unless they have been together with some pressure, very humid and for a too long time, you should be lucky with this method. Just make sure that when freezing, you don't add more humidity to the photos (e.g. put them in a sealed plastic bag with a bag of silica gel)

Whatever you do, do not heat them up (e.g. you might think you can get rid of the humidity that way; actually the humidity still in there will help with the freezer method)! Gelatin starts completely dissolving in cooking procedures at 50°C and will start chemical degeneration at 80°C but prolonged exposure to anything above 50°C is not a good idea already.

For the real bad sticking pictures, you might want to assist the tearing process with a thin razor blade. Be gentle. Bend the paper a bit and wait, the breaking of the gelatin might take a moment, but when you rip them apart, the chances are higher that it will not break at the surface.

---

Addendum to answer the follow up about if its a good idea to "make them a little wet again".

Out of experience, I would not recommend it, at least not in the way you make it sound like ("make them a little wet again" sounds like you want to spraw water on them or so).

Ideally you would want to make exactly those parts of the surface wet again that are sticking the most firmly to the next sheet of paper. Unfortunately due to that, those are the hardest to reach spots. Unless you have access to a humidor (or similar environment) to increase humidity in a very controlled way over a rather long time, adding any humidity will likely cause even more damage before it reaches the points where we want to have it soon enough.

Especially when you do not apply some tension to the photos while adding humidity, you will also add humidity to parts that are not sticking yet, and will make them sticky and possibly stick even more together at those parts.

If you are somehow able to apply the right amount of force, and add humidity in the right way to that one page of an album, you might be able to get better results than with the freezer method. Especially when the material sticking to the photos is rather porous and is too much embedded into the gelantin layer already. But this all opens much more room for error.

Especially in your case (when I understood you correctly, you have the two color faces of the photos stick together) the risk of more material mixing due to added humidity to the gelatine seems rather high, compared to breaking the gelatin at the hopefully rather weak points.

But just like in archeology (and somehow we seem to be approaching that topic here in a way) without inspection by an expert (and I am by no means one for these kinds of recovery, my photo recovery expertise is based on digitals) there is unlikely an outstanding clear way to approach this. Even the experts might want to try both methods with a small sample and see how it turns out.