NOTE: Please see the original version of this post and related discussion HERE. Cross-posted here per suggestion of Vitaliy Kaurov.

You will find a lot of information in this answer. I will add a few personal notes.

Module

Use Module when you want to localize variables inside your function's body, and those variables will potentially acquire and/or change their values during the computation.

Basic use

For example:

f[x_]:=Module[{y=x^2},y=y+x;{x,y}]

Here, a local mutable variable (symbol) y is local to the Module, and is, indeed, a symbol with a unique name. This is the closest you have in Mathematica to, say, local variables in C.

Advanced uses

Module also has advanced uses. One of them is to create closures - functions with a persistent state. My third post in this thread illustrates many cases of that and has further references. One example I will steal from there: the following function will produce the next Fibonacci number on demand, and yet it will be as fast as the iterative loop implementation for generation of consecutive Fibonacci numbers (since Module is invoked only once, when the function is defined):

Module[{prev, prevprev, this}, 
   reset[] := (prev = 1; prevprev = 1); 
   reset[]; 
   nextFib[] := (this = prev + prevprev; prevprev = prev; prev = this)
];


reset[]; 
Table[nextFib[], {1000}]; // Timing 

(* 
  ---> {0.01, Null} 
*)

One problem with persistence created with Module-variables is that one should not generally serialize such state (definitions), for example by saving the state via Save or DumpSave. This is because, the uniqueness of names for Module-generated symbols is guaranteed only within a single Mathematica session.

Module also allows one to create local functions, which With does not (except pure functions). This is a very powerful capability. It is particularly useful for writing recursive functions, but not only. In the link mentioned above, there were examples of this. One problem with local functions created by Module is that these symbols won't be automatically garbage-collected when Module finishes (if they have DownValues, SubValues or UpValues. OwnValues are fine), and so may lead to memory leaks. To avoid that, one can Clear these symbols inside Module before returning the result.

With

Use With to define local constants, which can not be changed inside the body of your function.

Basic use

For example,

f[x_,y_]:=With[{sum = x+y},{sum *x, sum *y}]

It is instructive to trace the execution of f. You will notice that sum gets replaced by its value very early on, before the body starts evaluating. This is quite unlike Module, where variable entries get replaced by their values in the process of evaluation, just as it would normally happen were the variables global.

Advanced uses

On an advanced level, With can be used to inject some evaluated code deep into some expression which is otherwise unevaluated:

With[{x=5},Hold[Hold[x^2]]]

(*
    Hold[Hold[5^2]]
*)

and is thus an important meta-programming tool. There are lots of uses for this feature, in particular one can use this to inject code into Compile at run-time right before compilation. This can extend the capabilities / flexibility of Compile quite a bit. One example can be found in my answer to this question.

The semantics of With is similar to that of rule substitutions, but an important difference is that With cares about inner scoping constructs (during variable name collisions), while rules don't. Both behaviors can be useful in different situations.

Module vs With

Both of these are lexical scoping constructs, which means that they bind their variables to lexical their occurrences in the code. Technically, the major difference between them is that you can not change the values of constants initialized in With, in the body of With, while you can change values of Module variables inside the body. On a deeper level, this is because With does not generate any new symbols. It does all the replacements before the body evaluates, and by that time no "constant symbols" are at all present, all of them replaced with their values. Module, OTOH, does generate temporary symbols (which are normal symbols with an attribute Temporary), which can store a mutable state.

Stylistically, it is better to use With if you know that your variables are in fact constants, i.e. they won't change during the code execution. Since With does not create extra (mutable) state, the code is cleaner. Also, you have more chances to catch an occasional erroneous attempt in the code to modify such a constant.

Performance-wise, With tends to be faster than Module, because it does not have to create new variables and then destroy them. This however usually only shows up for very light-weight functions. I would not base my preference of one over another on performance boosts.

Block

Basic use

Block localizes the value of the variable. In this example, a does not refer to i literally inside Block, but still uses the value set by Block.

a:=i
Block[{i=2},a]
{a,i}

Block therefore affects the evaluation stack, not just the literal occurrences of a symbol inside the code of its body. Its effects are much less local than those of lexical scoping constructs, which makes it much harder to debug programs which use Block extensively. It is not much different from using global variables, except that Blockguarantees that their values will be restored to their previous values once the execution exits Block (which is often a big deal). Even so, this non-transparent and non-local manipulation of the variable values is one reason to avoid using Block where With and / or Module can be used. But there are more (see below).

In practice, my advice would be to avoid using Block unless you know quite well why you need it. It is more error-prone to use it for variable localization than With or Module, because it does not prevent variable name collisions, and those will be quite hard to debug. One of the reasons people suggest to use Block is that they claim it is faster. While it is true, my opinion is that the speed advantage is minimal while the risk is high. I elaborated on this point here, where at the bottom there is also an idiom which allows one to have the best of both worlds. In addition to these reasons, as noted by @Albert Retey, using Block with the Dynamic - related functionality may lead to nasty surprises, and errors resulting from that may also be quite non-local and hard to find.

One valid use of Block is to temporarily redefine some global system settings / variables. One of the most common such use cases is when we want to temporarily change the value of

$RecursionLimit

or

$IterationLimit 

variables. Note however that while using

Block[{$IterationLimit = Infinity}, ...] 

is generally okay, using

Block[{$RecursionLimit = Infinity}, ...] 

is not, since the stack space is limited and if it gets exhausted, the kernel will crash. A detailed discussion of this topic and how to make functions tail-recursive in Mathematica, can be found e.g. in my answer to this question.

It is quite interesting that the same ability of Block can be used to significantly extend the control the user has over namespaces/symbol encapsulation. For example, if you want to load a package, but not add its context to the $ContextPath (may be, to avoid shadowing problems), all you have to do is

Block[{$ContextPath}, Needs[Your-package]]

As another example, some package you want to load modifies some other function (say, System`SomeFunction), and you want to prevent that without changing the code of the package. Then, you use something like

Block[{SomeFunction}, Needs[That-package]]

which ensures that all those modifications did not affect actual definitions for SomeFunction - see this answer for an example of this.

Advanced uses

Block is a very powerful metaprogramming device, because you can make every symbol (including system functions) temporarily "forget" what it is (its definitions and other global properties), and this may allow one to change the order of evaluation of an expression involving that symbol(s) in non-trivial ways, which may be hard to achieve by other means of evaluation control (this won't work on Locked symbols). There are many examples of this at work, one which comes to mind now is the LetL macro from my answer to this question.

Another more advanced use of Block is to ensure that all used variables would be restored to their initial values, even in the case of Abort or exception happening somewhere inside the body of Block. In other words, it can be used to ensure that the system will not find itself in an illegal state in the case of sudden failure. If you wrap your critical (global) variables in Block, it will guarantee you this.

A related use of Block is when we want to be sure that some symbols will be cleared at the end. This question and answers there represent good examples of using Block for this purpose.

Variable name conflicts

In nested scoping constructs, it may happen that they define variables with the same names. Such conflicts are typically resolved in favor of the inner scoping construct. The documentation contains more details.

Block vs Module/With

So, Block implements dynamic scoping, meaning that it binds variables in time rather than in space. One can say that a variable localized by Block will have its value during the time this Block executes (unless further redefined inside of it, of course). I tried to outline the differences between Block and With/Module (dynamic vs lexical scoping) in this answer.

Some conclusions

• For most common purposes of variable localization, use Module
• For local constants, use With
• Do not ordinarily use Block for introducing local variables
• All of the scoping constructs under discussion have advanced uses. For Module this is mostly creating and encapsulating non-trivial state (persistent or not). For With, this is mostly injecting inside unevaluated expressions. For Block, there are several advanced uses, but all of them are, well, advanced. I'd be worried if I found myself using Block a lot, but there are cases when it is indispensable.