You can climb a hill without knowing the gradient, so long as you can compare two points in terms of height. You randomly move in some direction, then compare the new point to the old point, go to whichever of them is higher, and repeat.

This sounds like what the experimenters are doing. Perhaps the GP was alluding to "first order hill climbing" as evaluating the gradient in every direction and climbing the steepest one, but the "0th order" version is also usually considered hill climbing and is better for some classes of problem.

That is exactly what they're doing. See the section on Exploratory Technique, second to last paragraph. As I said above, the possible innovation here is they can change midstream the criteria one uses to decide what is a "better shot".

is it picking a new configuration at random, or does it still have to be "close" to the last configuration?

It still has to be close by some metric to be considered hill climbing. The article doesn't make it clear, but I suspect a lot of the insight in the algorithm is how the computer chooses two similar sets of inputs that differ in an "interesting" way.

last clarifications, sorry.

Some manifold has a goodness function defined on it, described by a (totally ordered?) relation provided by the observing scientist.

The goodness function is assumed to be (continuous/differentiable/continuously differentiable?) with respect to some metric, and the computer picks a random coordinate within some small distance of the last coordinate in the metric, and then asks the human to order them?

I don't think this is hill climbing, and my simple reasoning for that is that I don't believe the first assertion. The expert is almost certainly behaving non-deterministically. In fact, I believe that each time the expert is presented with the "same" pair of coordinates, he is more likely to yield a different ordering.

That said, I could be reading this wrong.

The naive way to do calculus. Use secants to approximate the tangent. I think it's called finite difference.

Finite differences, you estimate the gradient.