First let me say that what is intuitive to a physicist may be not be so to a geometer and vice-versa. To many physicists a connection is the potential of a field satisfying a gauge invariance. For this point of view I refer to vol. 1, Chap. 6 sect 41 of the three volume book by Dubrovin-Fomenko-Novikov: Modern Geometry-Methods and applications.

I find this point of view less intuitive only because I was trained as a mathematician.

The notion of covariant derivative appears naturally when one tries to solve the following problem. Suppose that $E\to M$ is a smooth vector bundle over a smooth manifold $M$. For example, $E$ could be the tangent bundle of $M$. We seek a notion of parallel transport that will allow us to compare vectors situated in different fibers of the bundle. More precisely, this is a correspondence that associates to each smooth path

$$\gamma: [a,b]\to M$$

a linear map $T_\gamma$ from the fiber of $E$ at the initial point of $\gamma$ to the fiber of $E$ over the final point of $\gamma$

$$T_\gamma: E_{\gamma(a)}\to E_{\gamma(b)}.$$

The map $T_\gamma$ is called the **parallel transport along the path $\gamma$**.The assignment $\gamma\mapsto T_\gamma$ should satisfy two natural conditions.

(a) $T_\gamma$ should depend smoothly on $\gamma$. (The precise meaning of this smoothness is a bit technical to formulate, but in the end it means what your intuition tells you it should mean.)

(b) If $\gamma_0: [a,b]\to M$ and $\gamma_1:[b,c]\to M$ are two smooth paths such that the initial point of $\gamma_1$ coincides with the final point, then we obtain by concatenation a path $\gamma:[a,c]\to M$ and we require that

$$T_\gamma= T_{\gamma_1}\circ T_{\gamma_0}. $$

Suppose we have a concept of parallel transport. Given a smooth path $\gamma:[0,1]\to M$ and a section $\boldsymbol{u}(t)\in E_{\gamma(t)}$, $t\in [0,1]$ of $E$ over $\gamma$, then we can define a concept of derivative of $\boldsymbol{u}$ along $\gamma$. More precisely

$$ \nabla_{\dot{\gamma}} \boldsymbol{u}|_{t=t_0}=\lim_{\varepsilon \to 0} \frac{1}{\varepsilon} \left( T^{t_0,t_0+\varepsilon}_\gamma \boldsymbol{u}(t_0+\varepsilon)- \boldsymbol{u}(t_0)\right), $$

where $ T^{t_0,t_0+\varepsilon}_\gamma$ denotes the parallel transport along $\gamma$ from the fiber of $E$ over $\gamma(t_0+\varepsilon)$ to the fiber of $E$ over $\gamma(t_0)$. The left-hand-side of the above equality is called the covariant derivative of $\boldsymbol{u}$ along the vector field $\dot{\gamma}$ determined by the parallel transport. Thus, a choice of parallel transport leads to a concept of covariant derivative.

Conversely, a covariant derivative $\nabla$ leads to a parallel transport. Given a smooth path $\gamma:[0,1]\to M$ the parallel transport

$$T_{\gamma}: E_{\gamma(0)}\to E_{\gamma(1)} $$

is defined as follows. Fix $u_0\in E_{\gamma(0)}$. Then there exists a unique section $\boldsymbol{u}(t)$ of $E$ over $\gamma$ satisfying

$$ \boldsymbol{u}(0)=u_0,\;\;\nabla_{\dot{\gamma}}\boldsymbol{u}(t)=0,\;\;\forall t\in [0,1].$$

We then set $\newcommand{\bu}{\boldsymbol{u}}$

$$T_\gamma \bu_0:= \boldsymbol{u}(1).$$

This construction allows us to define the covariant derivative $\nabla_X\bu$ of a section $\bu$ of $E$ along a vector field $X$ of $M$. It satisfies the rescaling property

$$ \nabla_{fX}\bu=f\big(\nabla_X\bu\big),\;\;\forall f\in C^\infty(M). $$

A connection on $TM$ will then satisfy

$$\nabla_{fX} Y=f\big(\nabla_X Y),$$

for any vector fields $X,$ and any smooth function $f$. On the other hand the Lie derivative satisfies
$$
L_{fX} Y= fL_XY-(Xf) Y,
$$
so it cannot be a covariant derivative.

cannotdefine the Lie derivative of a vector field $X$ along a curve $y(t)$; at the very least you need to have a congruence, instead of just a single curve). $\endgroup$ – Willie Wong Sep 12 '11 at 14:01