I understand that the energy come from the magnetic's electromagnetic field, but how does the magnet produce that? Does it come from the Earth's field?
From the same place that a falling rock does.
Like gravity, magnetic forces are conservative, and they are not sources of free energy. Thus, when two magnets snap together, they are performing work on each other and thereby liberating energy, but if you want to get them back to where they started you will need to put in an equal amount of work when you pull them apart. This is exactly as with gravity: a falling rock might liberate energy as it falls, with gravity performing work on it, but if you want to get it back to where it started, you will need to perform an equal amount of work on the opposite direction.
You might also ask how they get the energy to perform that initial burst of work, and the answer is equally simple. Take two bits of iron, and they won't attract, but if you magnetize them then they suddenly start trying to perform work to attract each other. Where did that energy come from? Easy: it takes energy to magnetize them, and it's part of that energy that gets used in the attraction (and which gets replenished as you pull the magnets apart).
The energy is not in the earth's magnetic field in your example. It is in the magnet's magnetic field. The earth's field is smaller than the magnet's typically, so a reasonable magnet near a needle will pull it to it. A magnetic moment being acted upon by a magnetic field can indeed do work. That is why two magnets attract and move each other.
Should not be strange that the magnetic field has energy. The gravitational field also does, and you see it when the earth attracts a body making it come down, changing to kinetic energy. In conservative systems or forces, there is a potential whose negative gradient is the force.
It is true that the magnetic field of a magnet is due to the little spins inside, each one thus having a magnetic moment, aligning and thus adding up and causing a macroscopic magnetic field. Wherever there is a magnetic field there is energy. Same for electric field, which will accelerate charges. Or the combination of electric and magnetic field, which can radiate, carry energy, and use that energy to carry a signal so you can watch TV.