The Method of Exhaustion is not a method, and exhaustive in a very particular sense.
So what is it?
The Method of Exhaustion is a proof technique in Euclidean geometry that was developed in the 4th century BC by Eudoxus of Cnidus. It remained the most powerful method of proof available in geometry for more than two millennia.
In the fourth century BC Greek mathematicians had for a long time been trying in vain to square the circle, one of the three classical problems of antiquity. One can get the impression that this was a rather pointless (if curious) exercise in geometry, but the fact is that the problem had rather deep implications.
It is intuitively obvious that a circle encloses an area in the same way as a square or a rectangle does. Being mathematicians the Greeks did, however, not accept this but demanded some sort of proof. After all, if you cannot circle-line construct a square that is equivalent to a given circle, how do we know that they have the same "kind" of area? More generally: how do we know that curvilinear area is the same as rectilinear area and has the same properties? In fact: how do we prove anything about curvilinear area at all?
Development of the Method of Exhaustion
In the late 5th century BC people like Antiphon and Bryson had the notion that inscribing polygons with a larger and larger number of sides in a circle would "exhaust" its area and that the area of the circle is therefore not fundamentally different from that of the polygons.
About 380-370 BC Eudoxus produced a rigorous argument along the same lines and thereby resolved the issue. There are, however, no surviving writings of Eudoxus's, so the attribution and dating is from other sources. It still seems rather secure though, unlike e.g. all those bogus attributions to "Pythagoras".
The oldest surviving use of the Method of Exhaustion is Proposition XII 2 of Euclid's Elements (about 300 BC). This theorem was first proved by Eudoxus, but it seems likely that Euclid adjusted the proof slightly to fit his needs. The Method of Exhaustion was further developed and effectively used by Archimedes (middle 3rd century BC), and his version is believed to lie closer to Eudoxus's original one.
Until the arrival of the calculus in the 17th century the Method of Exhaustion remained the only technique available for dealing with curvilinear areas and volumes.
How it works
The Method of Exhaustion provides a way to prove rigorously that an area (or volume) A is equal to another area (or volume) B. The proof works by assuming otherwise, closely in- and/or exscribing simpler areas in/outside A and then deriving a contradiction.
This is fact one of the earliest applications of proof by contradiction, and it marks a development of the Greek notion of proof, from using only circle-line construction methods to also using proof "by logic". It was probably not the first use of proof by contradiction, but Proposition XII 2 of Euclid's Elements is the oldest application of proof by contradiction that there is record of.
Another thing to note is that while we can prove that A = B, the Method of Exhaustion gives us no way to find B, i.e. it does not provide a heuristic. In this way it is similar to the principle of induction, which can often be used to prove that a true statement is true provided that we can find a true statement to prove.
This meant that the Greeks had to use some other heuristic to produce their theorems, but these were lost in time. When people in Western Europe looked at Greek mathematics in the 15th century they had to search for this lost heuristic, which resulted in coordinate geometry and the calculus. The lost heuristic was eventually found in the 20th century, but that is another story altogether.
A Method of Exhaustion proof
As a relatively easy example of how the Method of Exhaustion can be used I will outline the proof of Proposition XII 2 mentioned above. In order to do that we first need to state the important Exhaustion lemma (Euclid X 1): "If we repeatedly subtract more than half from a quantity then the remaining quantity will eventually be less than any preassigned value."
Proposition XII 2:
The ratio of the areas of two circles is as the ratio of the square of their diameters.
Proof:
Call the circles A, B and their diameters c, d. We prove the theorem by contradiction.
Suppose that the statement is false. Then there is some area S such that S : B = c2 : d2. WLOG A > S.
Inscribe a square in A. We can double the number of sides by putting an isosceles triangle on top of each side, and repeat this as many times as we like. It is clear that each time the area of the added triangles will be more than half of the remaining area between the circle A and the inscribed polygon. For this remaining area is the sum of circle segments, each of which is contained in a rectangle with twice the area of the added triangles.
Hence it is, by the Exhaustion lemma, possible to inscribe a polygon P in A such that the area between A and P is less than the difference between A and S. Thus P > S.
Inscribe a similar polygon Q in B. By Proposition XII 1 P : Q = c2 : d2 (which is rather obvious). Hence P : Q = S : B, and B : Q = S : P. Since Q is inscribed in B it is clear that B > Q, so therefore S > P.
But P was chosen so that P > S, so we have arrived at a contradiction.
Hence the theorem holds.
The observant and informed reader will notice a striking similarity between the phrasing of the Exhaustion lemma and the epsilon-delta formalism of modern analysis. It is tempting to look back at the Exhaustion lemma and think "So the Greeks had limits" or "Good work Eudoxus, you almost discovered the calculus". This way of looking at what mathematicians in the past did and interpret it in terms of what we know and consider important is a serious mistake, and it is responsible for all sorts of stupid misconceptions about the history of mathematics.
In the particular case of the Exhaustion lemma we should note that there is a huge difference between using a certain formalism to justify the use of limits and using a similar formalism to avoid the use of limits altogether.
Another mistake that is easy to make is to look at the Method of Exhaustion and say "Hey, this looks a bit like an integral". Indeed, Archimedes is not infrequently referred to as "the father of integration". This is completely wrong. Almost any method of dealing with curvilinear area is bound to include little rectangles and polygons. When you consider that integration when applied to geometry uses coordinate geometry, expresses curves in terms of equations, provides a heuristic and is defined through algebra and limits, then it becomes rather hard to imagine a method connected with area that has less to do with integration than the Method of Exhaustion.
Finally...
The Method of Exhaustion is not a method, or at least does not seem to have been perceived as such by the Greeks. When they proved something using the Method of Exhaustion they imitated similar proofs; they did not think of it as a single coherent device to be applied to problems.
It is the way that the inscribed figures "exhaust" the area we wish to determine that has given the (non-) method its name.
You would be forgiven for thinking that the name referred to what using the method does to you. Since it was not packaged into a nice user-friendly algorithm the mathematician would have to set his Method of Exhaustion proof up from scratch every time. Writing out a full Method of Exhaustion proof for a non-trivial problem is a project that takes days.
The development of infinitesimal heuristics (led by Kepler) in Europe allowed mathematician to produce lots of new theorems. Proving them all would take ages, so when mathematicians published their results they left the proofs as exercises to the reader. Since nobody ever did those exercises mathematics temporarily lost very much of its rigorous nature. This was a problem, and the way to solve it was to formalise the use of infinitesimals into something that could be accepted as a method of proof, thereby getting rid of reliance on the cumbersome Method of Exhaustion. This was eventually achieved when Newton and Leibniz developed the calculus.