References and intro

First, let me point out that = is shorthand for Set and := for SetDelayed; this facilitates searching the docs. Also, as Simon Woods points out in a comment to the question, there is a tutorial on this.

Explanation

The basic distinction is this: y[x_]=expr means evaluate expr, then whenever you see y[something] evaluate evaluate what resulted. On the other hand, y[x_]:=expr means "whenever you see y[something], evaluate expr anew".

Here's how to see it:

a = 5;
y[x_] = a*x

y[3]
a = 10
y[3]
(*
15
10
15
*)

That is, when you define y, it evaluates the right hand side to 5*x and assigns that; if you change a later, it never sees it. On the other hand,

a = 5;
f[x_] := a*x

f[3]
a = 10
f[3]
(*
15
10
30
*)

Compare also:

?? y

So, the value of a at the time of definition has been "baked in", while with SetDelayed, we get

??f

that is, the value of a at execution time is what will be used.

Pitfalls

Here is an example where using SetDelayed results in a calculation being unnecessarily performed multiple times:

fsd[x_] := Integrate[z, {z, 0, x}]
gs[x_] = Integrate[z, {z, 0, x}];

If I try with a number, they give the same answer. But look at the DownValues:

??fsd

??gs

So, in gs, the integration has already been done, while in fsd it is performed anew every time fsd is evaluted. Observe:

t1 = Table[fsd[x], {x, 0, 1, .05}]; // AbsoluteTiming
t2 = Table[gs[x], {x, 0, 1, .05}]; // AbsoluteTiming
(*
{0.061729, Null}
{0.000061, Null}
*)

and t1 == t2 evaluates to True. The reason for the timing differences is precisely that the symbolic integration is done every time for one, only once for the other.

Another possible pitfall is using an already-defined symbold for the right hand side. For instance, consider the difference between these:

ClearAll[f, g];
x = 5;
f[x_] := Sin[x];
g[x_] = Sin[x];

f[1]
g[1]
(*
Sin[1]
Sin[5]
*)

A direct way to avoid this is to simply Clear the symbols that will be used as pattern names from the global context (ie, do ClearAll[x] in this example).

Memoization

As a final note, one may combine Set and SetDelayed to implement memoization. Here is how to calculate a Fibonacci number recursively, with

ClearAll[fib];
fib[1] = 1;
fib[2] = 1;
fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]

and without

ClearAll[fibnaive];
fibnaive[1] = 1;
fibnaive[2] = 1;
fibnaive[n_Integer] := fibnaive[n - 1] + fibnaive[n - 2]

memoization. The idea behind this is explained, for instance, here or here. You can also find some elaborations here.