A connection is an additional structure, or, simply speaking, a piece of information, that one may have in a vector bundle on a manifold.
What you are asking about is called technically a linear connection, i.e. a connection in the tangent bundle, so we are only discussing such connections here.
As @Zhen Lin pointed out, there are plenty of connections: just choose some $\Gamma^k{}_{ij}$ to be your Christoffel symbols in each coordinate patch, and then use the partition of unity argument to smoothly glue up the data.
Having a connection defined, you can then compute covariant derivatives of different objects. On functions you get just your directional derivatives $\nabla_X f = X f$. (Notice that this is true for any connection, in other words, connections agree on scalars).
On vector fields you get covariant derivatives in the sense that you mentioned in your question. The definitions are kindly provided by @Zhen Lin.
If you write down your vector fields in terms of a coordinate system, say $X=X^i \partial_i$ and $Y=Y^j \partial_j$, then \begin{align} \nabla_X Y &= \nabla_X (Y^j \partial_j) \\ &= \nabla_X (Y^j) \partial_j + Y^j \nabla_{X^i \partial_i} \partial_j \\ &= X(Y^j)\partial_j + X^i Y^j \nabla_i \partial_j \\ &= X(Y^j)\partial_j + X^i Y^j \Gamma^k{}_{ij} \partial_k\\ \end{align}
From this simple calculation you can see that the result $\nabla_X Y |_{p}$ of taking the covariant derivative at a point $p$ really depends only on the value of $X$ at point $p$, and of all values of $Y$ defined in a small neighborhood of $p$, as you would expect from a derivative.
You can then extend the notion of covariant derivatives to 1-forms, and then to arbitrary tensor fields: just use the Leibniz rule!
In Riemannian geometry we study manifolds along with an additional structure already given, namely, a Riemannian metric $g$. In this situation there exist a preferred choice of connection. Indeed, the Fundamental theorem of Riemannian geometry guarantees existence and uniqueness of a symmetric connection with respect to which the metric tensor is parallel $\nabla {g}=0$. It is called the Levi-Civita connection. In coordinates you know its Christoffel symbols and can compute covariant derivatives from the formulae provided in the answer of @Zhen Lin.
Geometrically, connection introduces the notion of parallel transport. Strictly speaking, we transport objects along curves, but vector fields induce some curves (integral curves), so one can speak about objects that are parallel along vector fields in this sense.