What's the difference between running up a hill and running up an inclined treadmill? Clearly there will be differences like air resistance; I'm not interested in that. It seems like you're working against gravity when you're actually running in a way that you're not if you're on a treadmill, but on the other hand it seems like one should be able to take a piece of the treadmill's belt as an inertial reference point. What's going on here?
 A: The word 'difference' may be ambiguous, but let's look at the situation from several points of view.
Energy balance: Indeed, your potential energy does increase in case 1 and not in case 2. Muscles clearly perform the same work, so the energy must go somewhere? Yes, to the electric grid. The treadmill device's engine, to maintain constant velocity, will consume less electrical power to do so (or might even push energy back into the grid, in case of an efficient motor) because your legs are actually pulling it now downwards. If you do the math, you see it exactly compensates.
Muscle work: work, in thermodynamical sense, is not just F*dx. One has to take a machine and consider all interfaces. For example, a spring or a muscle have two ends, and dx in the formula is actually the difference between two paths. Muscle expansion/contraction will be the same, and so is the force. Therefore, they are doing the same work. This work is, the amount of chemical internal energy stored within the muscle converted to mechanical work.
A: i get the impression this is something that doesn't need complicated physics to explain if you apply a quick common sense test first. if you step up a hill, you have to push the weight of your body upward with each step, or you do not continue moving forward.  if you are on a treadmill, you may place your foot forward, but at the same time you would be (on a hill) pushing against the higher point on the ground to move yourself uphill, the treadmill is conveniently lowering your foot back down to the starting point, so you didn't have to actually push yourself uphill very much before you  move on to the next step.  and it just continues like this, with the treadmill continuously re-lowering your step part way before you ever have the chance to expend that energy you'd need to genuinely push yourself uphill.  does anyone else see this?
A: Assume that the hill and the treadmill have the same angle of elevation (are inclined identically), and that two identical persons A and B are running on them at the same speed $v$. Here the speed of the person B running on the treadmill is obviously zero with respect to the ground, but we will consider the speed of the treadmill's belt to be $-v$.
Let's assume that B and the treadmill are now in a truck which is running up the hill parallel to A, and with the same speed $v$ as A. The truck should be arranged so that B and the treadmill are not inclined while the truck is running up the hill. By our hypothesis, the speed of the upper part of the belt is zero with respect to the ground. This will not affect the effort done by the runner B, because the truck is moving with constant velocity. That is, there are no extra forces caused by inertia, because the truck doesn't accelerate, decelerate or change direction.
By looking now at both runners A and B we see that they are moving parallel with the same speed. They can even do the same moves in synchrony. The angle elevation is the same for both of them too. But B may even not realize that he is climbing a hill, he may think that he is in a room with no windows, which doesn't move. The conditions are identical. So, there is no difference between them.
If our intuition still saids that the treadmill guy is burning less calories, let's imagine that the road on which the person A is running up the hill is a very long treadmill belt. Imagine that underneath the belt there is a treadmill which is doing two things: is moving with the same speed $v$ towards the top of the hill, and the upper side of the belt is moving backwards with $-v$, so that the belt appear to be fixed with respect to the ground. From the outside, the belt doesn't move (and for runner A too). Now, it should be clear that there is no difference.
In the above I assumed that there is no wind, the treadmill and the runners are moving with uniform speed, there is no difference between the runners. I also assumed that gravity is not weaker towards the top of the hill.
A: Let's get one thing out of the way: The work done against gravity is the same whether you are running on an inclined treadmill or running (at the same velocity) up a hill. You see this by considering the motion in the frame of reference of the runner - you can't tell whether you are moving up or the hill is moving down.
Yet the treadmill is easier for two reasons: wind resistance and coefficient of restitution. Let's start with wind resistance:
Approximate cross sectional area of body - 0.5 m^2 . Speed 2.5 m/s (uphill...). Coefficient of drag 1.2, density of air 1.2 kg/m^2. Drag force is $$F=\frac12\rho v^2 A c_d= 2.3N$$ so power loss due to wind resistance (treadmill vs real life) is only about 6W - a very small fraction of typical power expended.
The real difference lies in the way that the belt "stores" energy. When your foot strikes, it typically is just ahead of your body. With good form the point will be very close and little energy needs to be absorbed as the legs "shortens" while under stress. This is the major loss mechanism in running. When the treadmill replaces the road surface, two things happen: the belt has lower inertia so the runners body is not so decelerated by the impact; and the belt stretches and stores some of the energy elastically. This is where the energy saving comes from - what DMcKee called "easy on the knees".
A: For me it is axiomatic that machine miles are easier than real miles, but let's analyze the situation.
Assume the runner maintains a constant velocity up the hill, or remains stationary in the frame of the gym on the treadmill. In both cases the runner's acceleration is zero, so we know that her legs must provide a constant force with upward magnitude $mg$, and the they have to do this against a surface passing by at an angle $\theta$ below the horizontal and moving with a velocity $v$.
The kinematics in the runners frame of reference look the same. This is not the cause of the difference in perceived difficulty.
I have always assumed that the difference in difficulty was two fold:


*

*Wind resistance is not really negligible.

*The treadmill presents a very uniform reliable surface and the runner need not lift her legs as high to insure non-tripping progress.


Also modern treadmill are designed to be relatively easy on the knees, and the accomplish this by having a slightly springy feeling which presumably returns some energy to the runner.
A: Let's estimate some of the contributions discussed in dmckee's answer
Gravity
We can compute the power spent gaining altitude.
$$ W_\text{grav} = mg \dot h = m g v \sin \theta \sim m g v \theta $$
for small angles, with some typical numbers
$$ W_\text{grav} = ( 180 \text{ lbs} ) ( 9.8 \text{ m/s}^2 ) ( 1 \text{ mile} / 10 \text{ minutes}) ( 5 \text{ degrees} ) \sim 200 \text{ kcal/hr} $$
if I look up the energy burned running on the web, I get $800 \text{ kcal/hr}$.
So, it would seem, running a 10 minute mile on a 5 degree incline outside takes some 25% more work than on flat ground.
Air resistance
Next let's consider air resistance.  We have for its work
$$ W_{\text{air}} = \frac{C_d}{2} \rho A v^3 $$
with typical numbers
$$ W_{\text{air}} \sim (0.5) ( 1 \text{ kg/m}^3 ) ( 2 \text{ m} \times 0.5 \text{ m} ) * ( 1 \text{ mile} / 10 \text{ min} )^3 \sim 4 \text{ kcal/hr} $$
which is a much smaller effect. About 1/2 %
Non uniform surface
If we assume that running outside requires us to life our legs an extra 3 inches on average, the power contribution would be
$$ W_{\text{rough}} = m_{\text{legs}} g h_{\text{extra}} f_{\text{stride}} $$
with some typical numbers
$$ W_{\text{rough}} = ( 0.3 \times 180 \text{ lbs}) ( 9.8 \text{ m/s}^2 ) ( 3 \text{ inches } ) ( 2 / \text{ s}) \sim 30 \text{ kcal/hr} $$
which is larger than wind resistance but only a 4% increase over our base running number.
Springing of landing
What if the coefficient of restitution was different for the treadmill versus land, then everytime you impact you'd need to put in less energy springing off, its power saving should be
$$ W_{\text{spring}} = (\Delta r) m g (\Delta h_{\text{center of mass}}) f $$
with some numbers
$$ W_{\text{spring}} \sim  ( 10 \% )( 180 \text{ lbs} )( 9.8 \text{ m/s}^2 )( 6 \text{ inch} ) \sim 20 \text{ kcal/hr} $$
which is a roughly 3% change.
Not sure what to make of these yet...
A: I think the most significant difference between work done on an inclined treadmill and work done on a real incline is the gain in potential energy on the real incline. There is no real delta mgz on a treadmill, whereas if you fell back to your starting height from a real incline, you'd certainly notice a large amount of stored energy being turned into kinetic energy!
A: (Running up a treadmill) = (expend energy to keep feet moving at a constant speed) + (other effects)
(Running up a hill) = (expend energy to keep feet moving at a constant speed) + (energy to lift center of gravity by hill height) + (other effects)
A: What if the runner gets on her bicycle on the treadmill? Does she have to bike harder on an inclined treadmill than a horizontal one, both running at the same speed? 
(In this case, biking on a horizontal treadmill is almost effortless because on a bike, the real effort is the wind resistance, which would be non-existent in this case.) 
If the treadmill were turned off, and she stopped pedalling, she would start to accelerate backwards down the slope due to a component of her weight  $mg$ acting down the hill, namely $m g  \sin(\theta)$. 
The feeling on the (running) inclined treadmill at angle $\theta$ would be the same as biking on the flat (again with no wind resistance), but with an elastic strap or spring exerting a backwards force on the bike (equivalent to the component $mg \sin(\theta)$ of her weight, contingent on the required angle of ascent). Unlike the case on the flat without the elastic, she now has to press harder on the pedals to do work applying the appropriate force at the point of contact of the driving wheel at the appropriate speed. 
The arguments & conclusions for the bicycle carry over to the runner. But it is easier to imagine the situation for the bike, because it is less confused by the complicated motion of running.
A: For sake of argument I will compare a climber maintaining constant speed up a hill and a treadmill runner. If the climber suddenly stopped spending any amount of energy climbing the hill, gravity will tug on him as $mg sin \theta$ while additionally, friction acts in the same direction to slow him down. If a person on the treadmill does the same thing, not only is $mg sin \theta$ pulling him down, so will the friction in the same direction. In both cases they are countering the work done by these two forces so that there is no net change in kinetic energy. Assuming climber maintained the same amount of velocity at which the treadmill runs over, the friction should be perfectly identical with the only difference being what is moving relative to what. Hence there would be no difference in the energy spent neglecting the air drag, of course.
