Why is the gradient the best direction to move in? When optimizing a convex function, doing an update like:
$$w_{t+1} =w_{t}+ c\ \nabla(f(w)) $$ is recommended. Why is moving along $\nabla(f(w))$ the fastest way to move closer to the goal? What's the intuition around this?
 A: Your questions were: 


*

*Why is moving along $\nabla \left( f\left(x \right ) \right )$ the fastest way to move closer to the
goal?

*What's the intuition around this?


They are not the same question.  A solid answer for the second, imo, leads to better engagement on the use, and on the first part.  It is also more accessible for someone trying to get the basics down reasonably well.
My answers are, in reverse order:
(Answer 2) The intuition driving this is "steepest ascent".  It is an assumption.
Some insight on going along the steepest direction can be seen in here:

This is from the "Topographic prominence" page on Wikipedia.
If you start near the bottom of Atkins hill, and want to take the fewest number of steps* to get to the top, then the steepest slope is a good approach.  By "*" I mean that a step is a projection on the topographical map.  It does not account for vertical distance, and assumes that if you want to be at some place, you can.  This is good for functions, but can take work when climbing mountains.
If, on the other hand, you start at the top of Atkins hill, and use gradient ascent, then you don't go to Great Pond Mountain.  You only stay where you are.  The "gradient" doesn't give you a direction to go.
We like the gradient "where you are" on mathematical surfaces, because it can be computed or approximated.  This is especially useful in places like neural networks or deep belief networks where the location of our destination peak isn't knowable when we start in on the problem.  Finding it isn't easy, but we have computers to compute many many gradients while looking for the optimal configuration of parameters.
Some ways to handle the weakness of the intuition include:


*

*multiple uniformly randomly located initial points, and record the
location and value of the highest result.

*Another is called simulated annealing.

*Conjugate gradient ascent isn't bad, it will get you to the peak of a
parabola quicker.

*Over and under-relaxation can also accelerate convergence.


Like many things in math, and also like many things in the human experience, it is not a bad initial assumption, it is false but useful, and with time and work you can overcome its weaknesses.
(Answer 1) For your question 1, the "why" is a more challenging answer.
It is more symbolically intensive.  One must talk about convex, and distance measures.  There are derivatives and such.  
One must also talk about what "fast" means.  The fewest steps is zero, and the only way to do that is to start there.  The second fewest is to know where it is, and take one step to get there.
There is a rule in optimal control that says "best" doesn't mean anything without a rubric.  If you say an approach is best, then the rubric can often be pulled out of the answer.  If you provide the problem and the rubric, then the approach that serves that rubric (assuming it exists) can often be determined.  We could show the rubric's under which this approach is "best".
Fastest can mean different things.  Do you mean fewest mathematical operations?  Shortest time given an infinite supercomputer?  Fast isn't strongly defined and I don't want to presume too much on your question.
Can you clarify what you are looking for in part (1) of your questions?
Update:
Using the method of Lagrange multipliers, the extremal values occur at critical points on the surface.  If you assume that you started "near enough" to one of the critical points then by moving to points that reduce the gradient at your location to zero, you move to the critical points. "Near enough", though hand-wavey, usually lets Taylor Series assumptions convert your surface to being locally quadratic. 
A: It's easiest to think about this first in 1D. If you're trying to minimize a function, and you know it decreases to the left and increases to the right, which direction would go in? Clearly, you would want to go left (especially if you knew that there was only one local min, as implied by convexity).
Now consider moving in higher dimensions. The first issue is what direction are we going to move in? Well, the concept of directional derivatives is required to make an informed decision. The basic idea is that the derivative of moving in a line in any direction is 
$ \nabla f(x) \cdotp u$
Where $u$ is the unit vector describing the direction. What is the value that minimizes this? $u = -\nabla f(x)$. Therefore, stepping in the direction opposite of the gradient vector is the direction that will mostly quickly reduce your objective function. Of course, this is only the steepest direction in a very tight neighborhood, so as Mark Stone points out, it is not necessarily an optimal way to chose a proposal step. 
A: For a simple, intuitive answer to your question, which is what you wanted:
You are more likely to find the sea by going downhill whenever you can, than by going uphill or by ignoring the gradient altogether!
That's exactly what water does, and why most of it ends up in the sea.
However, that is not always the case, as it could get stuck in a local lake or reservoir.  It all depends on the topography of your function, and whether there are any local minima that could act as traps, and whether there are any escape routes from those traps, like the rivers that lead from a lake into the sea.
Also, water will take a very indirect, meandering path around a hill, rather than the shortest path over the hill.
But still, if you want to find the sea as quickly as possible, then it's usually best to keep going downhill whenever you can.  Follow the gradient.  Follow the water.
A: Here's a short, intuitive answer. For any continuously-differentiable function $f:\mathbb{R}^n \mapsto\mathbb{R}$, the gradient vector evaluated at a point $x$, written $\nabla f(x)$, captures (amongst other things) the direction of maximal instantaneous change upwards. This is just one of the properties of derivatives. Take a simple parabola $f(x) = x^2$, $\nabla f(3) = 6$ points towards $+\infty$ (so the direction is positive). Similarly, $\nabla f(-3) = -6$ points towards $-\infty$ (so the direction is negative). Even at $x=-3$, the direction towards $+\infty$ is still going to result in function increase if you go far enough, but it's not the direction of instantaneous increase. Thus, in both cases, the derivative points towards the direction the function will increase most given where you're currently located.
Since the function is continuously differentiable (meaning $\nabla f$ is a continuous mapping) the direction of maximal instantaneous rate of change is exactly opposite the direction of maximal instantaneous decrease. So whichever way the gradient tells you to go, going the exact other way will necessarily provide instantaneous decrease (given the assumptions I stated).
The practical reason why we take the direction of instantaneous decrease as a good proxy for the direction pointing to the minima is simply because we don't know how the whole function looks (especially in higher-dimensions) to be able to say "the minima is over here" or "over there." If we did know where the minima is, then there's no reason to optimize (the problem is solved already).
Conclusion. Gradient descent is a way to keep decreasing the function value. Given the function is unimodal (i.e. quasiconvex), of which convex is a special case, we will necessarily get to where we want to go. In fact, even if it isn't quasiconvex, recent work out of UC Berkeley shows that, with random initialization, gradient descent will produce at least a local minimizer (not a saddle point) with probability one.

