If one considers the good old 'fridge' magnet as an example, one
observes that it does, and can, hold a considerable mass before being
overcome by gravity and falling to the floor. Yet it does this without
any apparent consumption of energy.
We can take that same magnet, pass it perpendicular to a piece of
copper wire and electrons flow in the copper conductor producing
electricity, yet that reaction required that motion be invoked and we
subsequently would call the result as kinetic energy.  In the fridge
magnet, the magnetic field of the magnet itself could be considered
potential energy yet there is the apparent lack of any motion, or more
specifically, 'work done' that would require the expenditure of
energy.  How is it then that the magnetic can oppose the force of
gravity - it would seem indefinitely - without 'consuming' any energy?
In a similar vein, a magnet will induce a magnetic field into a
ferrous object (such as the good old magnetic screwdriver) giving it
the same property: being able to pickup errant screws, holding onto
them and again preventing the mass of the screw(s) to counteract the
force of gravity without any apparent energy input while leaving the
strength (gauss) of the original magnet intact. As far as we (I) know,
no fridge magnet has ever 'succumbed' to gravitational forces and
relinquished its magnetic properties - at least not in human
observational time frames!  So, if this is not 'Kinetic' energy that
is keeping this fridge magnet (and its associated attached mass) from
falling to the floor because of gravity - then what is it?  If one
considers the tenets of basic physics: energy is neither created nor
destroyed, and "FORCE=MASS multiplied by ACCELERATION", then how can
this magnet continue to defy the force of gravity without doing any  
apparent "WORK"?  Many have tried to create the Perpetual Motion
'Machine' but to no avail - it simply exists as a fictional urban
myth.
The fridge magnetic would appear to be such although it perhaps does
not qualify since it is not moving per se.  Or is it?  It, and the
rest of earth is in fact moving in space time and many have concluded
that the universe is actually accelerating. Einstein in all his wisdom
was frustrated by not being able to wrap his head around gravity and
it was one enigma he took with him to his grave.  Today, the search
for the gravity answer is the 'holy grail' of theoretical physics
researchers. Could it be that the answer to the "fridge magnet"
analogy question is still elusive, or have I missed something
elementary here?  A tank of gasoline is clearly potential energy and
can do no work until ignited in an engine whereby once the process of
motion is invoked by the spark of the internal combustion engine which
proceeds to drive the apparatus (car) to a destination - UNTIL that
is, the gasoline is consumed - at which point it wilol obviously cease
to move until refuelled at the next gas station.
The fridge magnet on the other hand - appearing to be doing 'work'
because it relentlessly 'holds' itself and its appendages in
opposition to the gravitational force that conspires to bring it
crashing to the ground - does NOT need fuel.  Where then does it
continue (like the elusive perpetual motion machine) to derive its
mysterious 'power'?  Why do I 'torture' myself with this and why can't
I simply accept (and I do appreciate) my fridge magnets as the
'magical' entities that they appear to be?  I suspect though that
there is an answer and that its not merely a magician's 'trick'!
The question (questions!) provoked by the fridge magnet paradigm in my
mind go well beyond mere curiosity - if we can harness what might be
an unencumbered energy source that is at once "eco-friendly",
ubiquitously available (essentially free?) and that could be
practically implemented - it would change forever our relstionship
with Mother Nature (hopefully in a good way!) and break  our
dependence on non-renewable energy techologies which are literally
destroying our planet. And in the same vein, parting ways with the -
at times - despicable political implications of reliance on the
destabilising influence of the conventional energy sector controlled
substantially by despotic regimes that
are more than willing to take our money, and our good will, whilst
knifing us in the back because of their historical hatred of us, and
their religious fundamentalism.  So - thats the longer question. 
Blame it on the fridge magnet.
Your comments wilol be appreciated.

OK. according to this site: http://my.execpc.com/~rhoadley/magfree.htm 
there is no way to get "free" energy from magnets, and magnets are not
perpetual motion devices. I believe that non-permanent magnets are
obviously magnetized and can be de-magnetized. It's like if you have a
generator that powers a motor that powers the generator. With
permanent magnets, it's a bit trickier to explain but this technical
(in my opinion) paper does a good job of explaining why permanent
magents are not "free" sources of energy. Again, I'm not a physicist,
so please correct me if I'm wrong. I hope this helped!

I think the answer to your question is right here, where you write:

"The fridge magnet on the other hand - appearing to be doing 'work'
because it relentlessly 'holds' itself and its appendages in
opposition to the gravitational force that conspires to bring it
crashing to the ground - does NOT need fuel."

There isn't any work being done when "holding" a mass so that it
doesn't accelerate in a gravitational field. There's no difference, in
a thermodynamic sense, between a postcard being pressed against the
outside of a refrigerator door by a magnet (assuming the 'pressing'
force is enough to cause friction from allowing the whole thing from
sliding down the door), and a postcard resting on a table. There is
zero energy-conversion happening in either case. The mechanism of the
*force* production is different, but there are many ways of producing
force which don't involve ongoing energy conversion: magnetism is one,
the (slight) compression of the table leg supporting the top of the
table and thus the postcard is another, gravity is one, electrostatic
forces (static electricity), differential aerodynamic pressure as from
a static vacuum chamber,  the list goes on and on. There might be some
energy conversion during the initial generation of the force, but
there is no ongoing source or sink of energy involved in many of these
situations.

Magnetism is not energy. It's simply a 'mechanism'.

As a HS Science teacher I have a few comments.
1. No work is being done.  Work = Force x distance.  That said, since
the magnet is NOT moving (in relation to the force of gravity of
earth, which is where physics is based), it would not matter what the
force or size of the magnet was.
2. Power = work done over time.  So again, since there is no work
being done, there is NO Power.
3. Kinetic Energy is energy in MOTION, so again, the magnet is
stationary, therefore all energy is STORED, or Gravitational Potential
energy.

Now, if the magnet were to start sliding down the surface of 'fridge,
the energy would be transfered from potential to kinetic.  In this
case, there would then be work done (if minor), and power.
Go to Physicsclassroom for more information.

Firewolf is exactly right.
F=MA, but the F there is resultant force. Since there is no motion,
there is no resultant force. Gravity and the magnetic attraction
balance each other out perfectly.
It is all held as Gravitational Potential energy, in the mass, and as
soon as the resultant force is the weight of the object, it will
accelerate towards the ground at a value of g, converting GPE into KE.
Perpetual motion machines arent, as such, an aspect of science
fiction, it is quite real. Just impossible (practically) to obtain.
Very simply, an object similiar to the London Eye could easily be a
perpetual motion machine. The only things I can think of off hand that
prevents it from doing so is...
a) Wind resistance
b) Internal friction

Transformers are very highly efficient, I was taught at school they
approach 100% efficient (not quite exactly that, some flux is still
lost and some heating of lubricants still occurs).