Why do Lagrange Multipliers work?

$\nabla f$ is the direction you need to go (to increase the value of $f$), and $\nabla g$ is the direction you can't go (because that's the direction off the surface, and you need to stay on). When these point in the same direction, no possible movement makes any improvement.

I hope it's obvious that this is just a sloppy heap of intuition. Maybe it's a good exercise to figure out the qualifications that need to be made to make it closer to actually correct.

So this is largely extracted from the wikipedia article on the above (http://en.wikipedia.org/wiki/Lagrange_multiplier) but hopefully I can make it clear.

I find lagrange multipliers easiest to understand in terms of vectors, so the concepts described apply mainly to functions of 2 variables but I imagine the concepts generalise readily to higher dimensions. So for the below discussion pretend the $\nabla$ is $(\partial/\partial x,\partial/\partial y)$

If you have a function $f(x,y)$ describing a surface over the x,y plane, one possible representation would be as a series of contour lines, curves of constant $f$. Similarly, any constraint on the variable $x,y$ can be rewritten as $g(x,y) = c$. This equation describes a single contour line of $g(x,y)$.

In order to find a minima of $f(x,y)$ subject to a constraint $g$ we are attempting to find the position on $g$ which lies lowest on f. If you calculate values of $f$ moving along the contour $g$, $f$ must decrease as you approach the minima, and increase afterwards. At the minima the change in $f$ must be zero. For this to be true the contour represented by $g$ must be parallel to a contour of $f$, such that infinitesimally any motion along $g$ is along the contour of $f$ and doesn't change $f$'s value. Similar considerations apply to maxima.

Now we need to translate the above statements into something mathematical: the quantity $\nabla f$ points along the direction of fastest change in $f$ (http://en.wikipedia.org/wiki/Gradient), so must be a vector normal to contours of $f$ (otherwise a component of the vector would lie along a contour, where by definition f does not change). Similarly the quantity $\nabla g$ is normal to contours of $g$, and hence to the contour given by our constraint $g(x,y)=c$. Finding the point where contours of $g$ and $f$ are tangential is now easy. We just need to find the points where the normals to $f$ and $g$ are parallel $\implies \nabla f = \lambda \nabla g$ where $\lambda \in R$. Note that if there are multiple minima or maxima this should just fall out of the maths.