How do magnets store energy?

Magnets store energy within the magnetic field as a magnetic potential. The simplest example of this occurs when you pull two magnets apart. When you do this you're spending energy and storing that energy as potential energy in the magnetic field. When the magnets come back together the potential energy is converted back into kinetic energy.