Reductio ad absurdum or the contrapositive?
Although the other answers correctly explain the basic logical equivalence of the two proof methods, I believe an important point has been missed:
- With good reason, we mathematicians prefer a direct proof of an implication over a proof by contradiction, when such a proof is available. (all else being equal)
What is the reason? The reason is the fecundity of the proof, meaning our ability to use the proof to make further mathematical conclusions. When we prove an implication (p implies q) directly, we assume p, and then make some intermediary conclusions r1, r2, before finally deducing q. Thus, our proof not only establishes that p implies q, but also, that p implies r1 and r2 and so on. Our proof has provided us with additional knowledge about the context of p, about what else must hold in any mathematical world where p holds. So we come to a fuller understanding of what is going on in the p worlds.
Similarly, when we prove the contrapositive (¬q implies ¬p) directly, we assume ¬q, make intermediary conclusions r1, r2, and then finally conclude ¬p. Thus, we have also established not only that ¬q implies ¬p, but also, that it implies r1 and r2 and so on. Thus, the proof tells us about what else must be true in worlds where q fails. Equivalently, since these additional implications can be stated as (¬r1 implies q), we learn about many different hypotheses that all imply q.
These kind of conclusions can increase the value of the proof, since we learn not only that (p implies q), but also we learn an entire context about what it is like in a mathematial situation where p holds (or where q fails, or about diverse situations leading to q).
With reductio, in contrast, a proof of (p implies q) by contradiction seems to carry little of this extra value. We assume p and ¬q, and argue r1, r2, and so on, before arriving at a contradiction. The statements r1 and r2 are all deduced under the contradictory hypothesis that p and ¬q, which ultimately does not hold in any mathematical situation. The proof has provided extra knowledge about a nonexistent, contradictory land. (Useless!) So these intermediary statements do not seem to provide us with any greater knowledge about the p worlds or the q worlds, beyond the brute statement that (p implies q) alone.
I believe that this is the reason that sometimes, when a mathematician completes a proof by contradiction, things can still seem unsettled beyond the brute implication, with less context and knowledge about what is going on than would be the case with a direct proof.
Edit: For an example of a proof where we are led to false expectations in a proof by contradiction, consider Euclid's proof that there are infinitely many primes. In a common proof by contradiction, one assumes that p1, ..., pn are all the primes. It follows that since none of them divide the product-plus-one p1...pn+1, that this product-plus-one is also prime. This contradicts that the list was exhaustive. Now, many beginner's falsely expect after this argument that whenever p1, ..., pn are prime, then the product-plus-one is also prime. But of course, this isn't true, and this would be a misplaced instance of attempting to extract greater information from the proof, misplaced because this is a proof by contradiction, and that conclusion relied on the assumption that p1, ..., pn were all the primes. If one organizes the proof, however, as a direct argument showing that whenever p1, ..., pn are prime, then there is yet another prime not on the list, then one is led to the true conclusion, that p1...pn+1 has merely a prime divisor not on the original list.
I agree with Joel's answer: proofs by contrapositive are more satisfying than proofs by contradiction, because they give you more information beyond just knowing that the desired result is true. For instance, in analysis, proofs by contrapositive tend to be finitary in nature and yield effective bounds, whereas proofs by contradiction (especially when combined with compactness arguments) tend to be infinitary in nature do not easily yield such bounds (unless one very painstakingly converts each step of the infinitary contradiction argument into a finitary contrapositive argument). I discuss this for instance in
http://terrytao.wordpress.com/2008/08/30/the-correspondence-principle-and-finitary-ergodic-theory/
But by the same token, proof by contradiction is a more powerful method in practice than proofs by contrapositive, if your only aim is to prove the stated result; it is precisely because one is less ambitious that one can achieve one's goal more easily.
There is an analogy with the computational problem of trying to find a path in a maze from A to B. The direct approach would be to start from A and explore all reasonable-looking directions from A until one reaches B. The analogue of proof by contrapositive would be starting backwards from B and trying to reach A; then at the end one simply reverses the path. The analogue of proof by contradiction is a meet-in-the-middle strategy: explore both forwards from A and backwards from B until one gets an intersection. This is a faster strategy, with a run time which is typically the square root of the run time of the other two approaches (because of the birthday paradox, basically, or Metcalfe's law if you wish). This analogy is somewhat oversimplified because even in the meet-in-the-middle strategy it is not difficult to disentangle the solution to create a direct path from A to B; but with more complicated problem-solving tasks than mazes (e.g. trying to convert several hypotheses $A_1,\ldots,A_n$ into several conclusions $B_1,\ldots,B_m$, using deductive rules such as ``If $A_3$ and $C_5$ are true, then $D_7$ is true'', etc.) one can make the meet-in-the-middle solutions quite hard to convert back to a direct argument.
There is a class of proofs by contradiction that I call "no self-defeating object" arguments, which are particularly difficult to convert into proofs by contrapositive. Basically these proofs tend to show that A is false by using one argument to establish $A \implies B$ and another to establish $A \implies \neg B$, giving the contradiction (A defeats itself). One can convert this into a proof by contrapositive by making the inspired decision to divide into the two cases $B$ and $\neg B$, and show that each of these cases implies $\neg A$ by taking contrapositives of each side of the no-self-defeating object, but it is difficult in practice to motivate this choice of division into cases unless one had already seen the proof-by-contradiction version of the argument. This is particularly the case if A is an existence statement $\exists x: A(x)$ and B is dependent on x; then the dichotomy $B \vee \neg B$ cannot even be introduced without first introducing x. I discuss this type of argument on my blog at
http://terrytao.wordpress.com/2009/11/05/the-no-self-defeating-object-argument/
My answer applies to standard logic only.
In terms of standard logic, proofs by contrapositive and by contradiction are "equivalent" in that they are both logically valid, and two logically valid propositions are equivalent to each other.
On the other hand, it is certainly true that every proof by contrapositive can be phrased as a proof by contradiction. Indeed, since the latter is perhaps a bit more intuitive, it is often used as a justification of the former when it is needed e.g. in calculus courses:
We wish to show $A \implies B$. Suppose we know that $\lnot B \implies \lnot A$. Suppose further that $B$ is false. Then $\lnot B$ is true, so $\lnot A$ is true, so $A$ is false, contrary to our assumption.
Suppose a proposition can be proved by contraposition. As above, there is then a standard recipe for modifying the proof to give a proof by contradiction. However, if you compare the two proofs you find that the one by contradiction merely has the above two line argument appended to it, so it is just slightly longer without any additional content. For this reason, when it is possible to give a direct proof of $\lnot B \implies \lnot A$ it is preferable to do so, rather than casting it as a proof by contradiction.
However, proof by contradiction is a more powerful technique in the informal sense that some proofs are more difficult to phrase using contraposition. (I don't want to say impossible, because as above, both "techniques" are simply logically valid arguments, so may be inserted in a proof at any point.)
What makes contradiction potentially more powerful? (This is a question that you have to face when you teach introduction to proofs classes, as I have. I wouldn't have had as ready an answer before.) I think it is because we get to assume two things rather than one. Namely, instead of just assuming $\lnot B$ and using that one assumption to work our way to $\lnot A$, we get to assume both $A$ and $\lnot B$ and play them off one another in order to derive a contradiction.
Here is an example of this. Suppose we wish to prove that $\sqrt{2}$ is irrational. First, let's phrase this as an implication:
For all $x \in \mathbb{R}$, $x^2 = 2 \implies x \not \in \mathbb{Q}$.
Or, contrapositively:
For all $x \in \mathbb{R}$, $x \in \mathbb{Q} \implies x^2 \neq 2$.
Taking the contrapositive was not so helpful! What we need to do is work from both ends at once:
Suppose that $x \in \mathbb{Q}$ and $x^2 = 2$. Now we are in business; we can work with this. (I omit the proof since I assume that everyone knows it.)
Here is another difference between the two proofs, which I didn't notice until I thought about this answer: the contrapositive of the statement
$\forall x \in S, P(x) \implies Q(x)$
is
$\forall x \in S, \lnot Q(x) \implies \lnot P(x)$:
note that the quantifier has not changed. (Of course we might have an existential quantifier instead, and the discussion would be the same. Anyway, in practice most mathematical propositions do begin with a universal quantifier.)
However, the negation of the statement is
$\exists x \in S \ | \ P(x) \wedge \ \lnot Q(x)$.
Note that the quantifier has changed from $\forall$ to $\exists$, which is a key feature of the above proof.
Finally, you ask why we would prefer one technique over another since both are equivalent. But of course we do this all the time, according to convenience and taste: e.g. induction, strong induction and well-ordering are all logically equivalent, but we use all three. We could e.g. phrase all induction proofs as appeals to the Well-Ordering Principle, but in many cases that would amount to inserting a tiresome rigamarole "Consider the set $S = \{ n \in \mathbb{N} \ | \ P(n)\ \text{is false} \}$..." which does not add to the clarity or concision of the proof.