Why are the level curves of a function f perpendicular to its gradient?

(There's probably a clearer answer in the textbook, but...)

So the situation here is you have a function f(x,y,z), and you want to see that grad f is orthogonal to the level surface f(x,y,z) = c (I guess he's writing w for f(x,y,z), but whatever). And what you do is think about a curve contained in said level surface. You can parametrize the curve as r(t) = (r1(t),r2(t),r3(t)).
Now, the fact that the curve is contained in the surface means f(r(t)) = c for all t (i.e. f(r1(t),r2(t),r3(t)) = c -- it's a function of three vars, and my r(t) is a vector). Let's define a new function v(t) = f(r(t)), maybe this makes it easier to think about. v(t) = c for all t, so dv/dt = 0. Can't argue with that.
On the other hand, we can also compute dv/dt using the chain rule. It's f(r(t)), so you get
dv/dt = df/dx dr1/dt + df/dy dr2/dt + df/dz dr3/dt (some of those d's should be the funny partial sign, but you get the idea)
Rewrite that as
dv/dt = (df/dx,df/dy,df/dz) . (dr1/dt, dr2/dt, dr3/dt) = grad f . dr/dt
so grad f . dr/dt = 0, which is what we wanted. Because this means grad w is perpendicular to every vector tangent to the level surface in question (since any such vector is the velocity vector of some urve in the surface).

When you've found a critical point using Lagrange multipliers, how can you check if it's a maximum or a minimum?

This is a pretty subtle point to check. Here's one thing that will work most of the time: just write z as a function of x and y (using the constraint g) and plug that into f. Then you can use the usual second derivative test in x and y to figure out if you have a max or min (subject to the constraint). You could substitute out one of the other variables instead if it's easier.
The best case is that you can just look at it and tell if it's a max or min for some easy reason (as in all things on the homework). The book seems to steer clear of the whole question, and I think it's because it's a quite difficult point.
If neither of these work, things are quite a bit harder. Basically you'd want to do a constrained second derivative test, similar to the constrained single derivatives you saw in lecture. But this is going to be much harder -- the method of differentials isn't available. This question ties in to the notion of "curvature" -- the fact that the constraint surface isn't flat is what makes it so tricky. I don't see a simple way to check this in the general case, though let me know if you spot one!