The major use (that I see at least) for anonymous functions using the & notation is to introduce functions within expressions instead of declaring them on their own. For example, maybe you have a list of numbers and want to turn it into a list where each number is replaced with the result of some predicate (like >4). You could do this by using an anonymous functions like this:
In[1]:= # > 4 & /@ {1, 2, 3, 4, 5, 6}
Out[1]= {False, False, False, False, True, True}
This idiom is common for things like mapping a function over a list, or defining a predicate used by other functions like Select:
In[2]:= Select[{1, 2, 3, 4, 5, 6}, # > 4 &]
Out[2]= {5, 6}
In both of these cases the function being defined just has one parameter, and is equivalent to this function using the other notation that you mentioned:
In[3]:= f[x_] := x > 4
In[4]:= Select[{1, 2, 3, 4, 5, 6}, f]
Out[4]= {5, 6}
The advantage of defining a named function like that is that you can use it over and over without restating the body of the function. Anonymous functions are useful when the function serves some transient purpose where you don't want to declare it as a named thing.
This idiom is common in functional languages: the concept of introducing anonymous (or pure) functions is used all over the place in languages that support what are usually called lambdas. If you look around at, say, OCaml or Haskell or F#, you'll see the term lambda used in a very similar manner as pure functions in Mathematica.
I don't believe it's correct to think of the & symbol as "anding" the body of the function with its arguments. The symbol is there more or less to tell the system where the declaration of the function ends. For example, I can say this:
In[1]:= (#^2 & /@ #) &[{1, 2, 3, 4}]
Out[1]= {1, 4, 9, 16}
In that case there are two anonymous functions being defined in different places: the innermost one defines the function being mapped over some list that squares the elements. That is then wrapped up inside another function where the argument is the list to map over. So, the position of the & really is more of a delimiter indicating where the functions are defined. It's a little easier to see this when you look at things in TreeForm:
(#^2 & /@ #) & // TreeForm

I doubt there is a performance difference, but that would require some more knowledge of the internals of how the interpreter handles functions.