Stored energy and momentum in a magnetic field?
Here is how I think about this intuitively (I assume you know the mathematical formulation, but that doesn't necessarily help with the intuition; so forgive the deliberately imprecise language I am about to use).
When you have a very low magnetic field, you draw field lines far apart. As the field increases, the field lines come closer together. Now if you think of field lines as repelling each other, this is akin to compressing a gas by adding more molecules to a volume: as you add more molecules, the pressure goes up, and the energy stored in the gas goes up. Every time you add another molecule you have to work against a greater pressure, so energy stored goes as pressure squared. The same thing for magnetic fields: if you consider the field lines as repelling, then "adding another field line" to a bunch that's already there (for instance, inside your current loop) requires you to do work - the larger the field, the more work it is to add another line.
And if you allow the magnetic field to "escape" (akin to the gas expanding), the change $\frac{dB}{dt}$ will result in the induction of currents and voltages, and work being done - that's how the energy can be extracted again.
To answer your question it takes a little bit longer as usual.
Let us start with permanent magnets. Where the magnetic field of permanent magnets come from? The process of its production is the next: Some material is milled to powder, then it will be pressed into its form under the influence of a strong magnetic field and sintered. Why this we do? The best materials we can use for strong permanent magnets are molecules with a high dipole moment. Under the influence of the external magnetic field they get aligned and in this state the stay "frozen" after the sinter process.
To finish this point you will ask, why molecules have magnetic dipole moments. This is because every electron as well as every proton (and neutron too) has a magnetic dipole moment. This is an intrinsic property (as well as the electric charge of electrons and protons and for their anti-particles and as well as the intrinsic spin). The magnetic moment of molecules is somehow the sum of the magnetic dipole moments of the constituents.
To align the magnetic dipole moments of the powder it is needed energy. From this thought only, it is necessary that to bring the material into the external magnetic field it is needed to do work. And, once aligned and "frozen", the magnet is under tension. Never drop a strong permanent magnet, it will explode in pieces.
What for a energy content you are able to extract from the interaction of two permanent magnets? Bringing antipodes together, it is easy to answer the question. You store and gain energy in the same way as in a spiral spring between two cylinders or - as Flores stated - in a gas spring. Bringing a north and a south pole of two magnets together, you gain eneregy. To take them apart, you lose the energy again. Following all this processes with permanent magnets one has to conclude that you couldn't gain energy from permanent magnets without destroying them (and realising the energy that was put in during production). In all other cases you have to put in motional energy first. Perhaps it is more complicated than described here.
Now about electromagnets. Again we have to take in account the magnetic dipole moments of the involved particles. Making a coil from a wire you will not have any magnetic field. Only after you send electrons through the wire (by the help of a electrostatic potential difference, which let flow the electrons from the source to the sink, called current), a magnetic field will built up. How this could happen? I don't want to repeat what I explained about the induction of a magnetic field by the alignment of the magnetic dipole moments of the involved - moving in an accelerated way - electrons.
It is important to state that the magnetic field of such a coil gets stronger when more electrons flow through the - bended into a spiral - wire (in some limits according to the ohmic resistance and heat loses). But the work of such a magnet will be done by the electric current. By inserting a iron core into the coil the magnetic field can be enhanced. Doing this the resistance (not the ohmic, it is call the inductive resistance) of the coil increases, the electric source is responsible for this.
About your second part of the questions. The Lorentz force transforms the kinetic energy of moving charged particles into a deflection (and this a acceleration again). The external magnetic field is the moderator or catalysator but do not gain nor store energy for long times from the moving particles. That is easy to prove. A permanent magnet of the same strength as a electromagnet induces the same Lorentz force of moving charged particles and the permanent magnet meanwhile don't lose its magnetic field strength. The conversion of the kinetic energy to heat works by the way, I explained in the above link.
Long speech, short sense. Magnetic and electric fields do not interact direct. In all induction phenomenons (induction of a current in a generator, generation of a magnetic field by the movement of a conductor transversely to the current direction and Lorentz force) one field could induce the other field. But never an electric charged body (if this body is not magnetizable) will be attracted by a magnetic field nor a magnet will be attracted by a electric field (if this body is not polarizable).