Great question. I'll skip the warmup and go right to your key point: where does the field energy come from?
Typical permanent magnets are made deliberately. Some magnetic material is heated up, a magnetic field applied, and then the material cools in the field. Lots of energy is wasted in this process, but let's follow just where the field energy is made. Initially the material has magnetic domains pointing in every direction, so their fields approximately cancel, leaving essentially no field energy outside the magnet. When a field is applied (usually via an electromagnet) to the warm material, it lines up the domains. It takes energy input to that electromagnet to do work lining up the magnetic domains. So the energy came from whatever supplied the electrical power.
Yes, the same sort of question could be asked about gravity or any field. Tracing the various energies in the universe back to shortly after the Big Bang, I guess you'd say that the big forms of energy then were the rest mass (energy) of particles (many of which then decayed) and the inetic energy of their relative motions, There are other ways of expressing and thinking about those energies, e.g. as field energies, however. As for how it all got started in some state, nobody knows. (Admittedly that's pretty much a non-answer.)
On your other question, you can tell when a lot of the field energy is gone because that's the same as when the field is much weaker. You'd notice that the next ball was not pulled in very much.
The total energy in the system also depends on the configuration of the balls. The energy in the field is directly proportional to the integral of the square of the field strength over the whole volume, plus terms from the interaction with the material. If you can arrange the balls to divert field lines farter away from the magnet and cause them to take longer paths around, then you have increased the energy of the system. An example of this -- a bar magnet with a bunch of iron balls will likely have its lowest energy content when a chain of balls lines up from one pole to the other, allowing the fringe field of the magnet to follow the chain of balls, reducing the field outside the region containing magnets and balls. If you move the balls around, say stack them up end to end all on the North pole of the bar magnet, then the energy of that configuration will be higher than the one I described above. You'd have to hold the balls in place with some other force, or they will eventually end up in their lower-energy configuration.
Some actions involve repulsive forces, where to bring in an an additional magnet, you must add energy.
(published on 08/21/06)