The second law of thermodynamics - about the increasing entropy - which is apparently what you're talking about - holds for any system. Permanent magnets are no exception.
A ferromagnet may look "more ordered" than a non-magnetic material because the spins are oriented in the same direction, rather than random directions. But physical systems may only try to maximize their entropy among configurations that conserve energy (much like the momentum, charge, and other conserved quantities). For ferromagnets, the configuration with spins oriented in random directions would have a much higher energy - because one reduces the energy by orienting the spins, elementary magnets, in the same direction.
So the spontaneous disappearance of the uniform electrons' spin would violate the energy conservation.
Among the configurations with the same energy, the magnet still tries to maximize its entropy. In particular, the heat is flowing from warmer pieces of the material to colder ones, and so on. More generally, the entropy never goes down, and that's the only general statement that follows from the second law of thermodynamics.
Ferromagnets are not special among physical objects that could have a higher entropy if you allowed the energy to increase. For example, any object would raise its entropy - the amount of disorder - if its temperature increased. But a higher temperature requires a higher energy, too. One can't violate the first law of thermodynamics (energy conservation) just because it would make it more straightforward to satisfy the second law. Both of them hold in Nature.
When you stack two identical permanent magnets, you get roughly the strength of one twice the size. However, a magnet twice the size has to spread its magnetic energy over twice the volume, so the surface strength of the magnet is rarely significantly increased. Smaller neodymium magnets that have the same rating typically have roughly the same surface strength as larger ones. What increases is the holding power, because they have larger surface area.
Best Answer
Yes, they can. Here is a nice article about preventing that:
Care & Feeding of your magnet