Yes, it is possible for a permanent magnet to lose its magnetism. There are three common ways for this to occur:
1) Via heat: ferromagnet materials will lose their magnetism if heated above a point known as the Curie temperature. At this point, the energy being put into the magnet from the heat will permanently disrupt the magnetic domain structure of the material, turning it into a paramagnetic material [a similar effect occurs in materials called hard ferrites, which exhibit a form of magnetism called ferrimagnetism; the analogous temperature for these materials is known as the Neel point]. You would have to re-magnetize the magnet again, either in a solenoid or with another permanent magnet, in order to restore the magnetism. If you heat a magnet up a little bit, it will lose some of its magnetism, but on returning to room temperature [depending on how high it was heated, and on the shape of the magnet itself], full magnetism can be restored.
2) Via a demagnetizing magnetic field: permanent magnets exhibit a characteristic called coercivity, which is the ability of a material to withstand being demagnetized by an applied magnetic field. Modern permanent magnet materials such as Sm-Co and Nd-Fe-B have high coercivities; older materials such as Alnico or ceramic [hard ferrite] materials have lower coercivities. With a strong enough magnetic field of opposite polarity, it is therefore possible to demagnetize the magnet [whether this comes from another permanent magnet, or a solenoid]. Interestingly, an opposing magnetic field is sometimes applied to a magnet in order to 'knock it down', or to lower its overall magnetic output, so that it can be used appropriately in an application.
3) Via shock: this really only applies to older materials such as magnetic steels and Alnico materials; the mechanism that creates coercivity means that they are susceptible to being demagnetized if enough energy is transmitted through the material via a shock, such as being dropped or hit with a hammer. Modern materials do not suffer this type of problem.
Gareth Hatch, Ph.D., Director of Technology - Dexter Magnetic Technologies