I have heard that it's possible for a permanent magnet to become too hot to function, especially if it reaches melting temperature however I cannot find much on the affect of cooling a magnet especially to temperatures around absolute zero.
In the case of permanent magnets, there are two effects of temperature on the strength of the magnet:
- saturation magnetization
Both of these will be larger at low temperature, a stronger magnet.
A ferromagnetic material will order below its Curie temperature, often because of interaction between localized magnetic moments. The magnetization is saturated at $0$ kelvin. At higher temperatures, thermal excitations will flip some local moments so that the magnetization is lower. At the Curie temperature the long-range order disappears and the material is paramagnetic. This does not have anything to do with vibrations of atoms. It just depends on the strength of the interaction and the temperature.
A permanent magnet has a high coercivity. This is because the domain walls are pinned by metallurgical structures. The coercivity also decreases at higher temperature.
Permanent magnets (ferromagnetic materials) arise from an emergent property of their structure. The exact physics of what makes certain elements magnetic is largely based on quantum mechanics and requires half-filled atomic orbitals etc. etc. etc.
The important thing to take away from this is that if an element has the right properties, then it will have a magnetic dipole, and act similarly to a really really really small bar magnet.
There are lots of elements that do this on the atomic level, but only a few ferromagnetic substances. Why is this? Well most of the time, the magnetic dipoles of the individual atoms are oriented randomly and so effectively cancel each other out. Every once in a while though, there will be a lattice structure in the substance that allows these magnetic dipoles to line up and add together to form a single, fully magnetic object.
What does this have to do with temperature!?
Let's deal with the hot stuff first. Remember that particles vibrate and that this vibration is essentially their temperature. Well, you might imagine that when atoms start to vibrate too much, they might not all align their magnetic moments anymore. This happens at what we call the Curie Temperature, at which point most magnets will very rapidly stop being magnetic.
On the other side of the coin, when you cool things down, they vibrate less. This means that on aggregate they are more aligned in their magnetic dipoles, and thus form a slightly stronger magnetic field than they would at room temperature.