Is there a way to define a Lie derivative of a connection? I've been reading a little bit about the definition of symmetries on General Relativity, and they are related with the concept of Killing vector, i.e., vectors along which the Lie derivative of the metric vanishes $\mathcal{L}_X g =0$.
However, afaik the most symmetric geometrical object is the Ricci tensor (see the post), and the a vector $X$ satisfying $\mathcal{L}_X \text{Ric} = 0$ is known as a collineation of the Ricci tensor.
I'd like to know whether is possible to define a sort of Lie derivative for a (general) connection, or a way to somehow define the symmetries of a connection.
 A: I was expecting the Lie derivative of a connection to be another connection but Vladimir's answer about the difference of two connections being a tensor makes a lot of sense. I would say a coordinate free algebraic formula for the Lie derivative of a connection is:
$\left(\mathcal{L}_{X}\nabla \right)_{Y}Z:=\mathcal{L}_{X}\left( \nabla_{Y}Z\right)-\nabla_{\mathcal{L}_{X}Y}Z-\nabla_{Y}\mathcal{L}_{X}Z$.
This is just the formula for the Lie derivative of a tensor and in this case it does give a $C^{\infty}(M)$-linear object in the variables $Y$ and $Z$. Since this is a tensor field probably a better notation would be
$\left(\mathcal{L}_{X}\nabla\right)\left( Y,Z \right)$.
A: Of course, yes. Lie derivative  is defined for any geometric object (= when it is defined what happends when we change a coordinate system): take the flow  $\phi_t$ of the vector field,   consider the pullback $\phi_t^*\Gamma$  of  your geometric object $\Gamma$ and define Lie derivative  as the $\tfrac{d}{dt}$-derviative at $t=0$ of  $\phi_t^*\Gamma$. 
For affine connection its Lie derivative is an (1,2)-tensor field. It is because derivative is more or less the same as difference and difference of two connections is a (1,2)-tensor field. 
Of course if the Lie derivative of a connection is zero then the connection is presered by the flow  so you vector field is a symmetry of the connection. 
Of course there exists an algebraic  formula for the Lie derivative in   terms of the components of an object in the coordinates ($\sim$ Christoffel symbols, for example), components of the  vector field, and their first derivatives. I do not remember this formula by hart but Maples DifferentialGeometry package knows it. It is a sum of  two terms, the first part is the usual formula of the Lie derivative for a (1,2)-tensorfield and the other part is something like the vector field plugged in the curvature.  
A: This tweet lead me to try to simplify Luis's answer.  A nicer formula is given by:
$$(Y,Z)\mapsto [X,\nabla_YZ]-\nabla_{[X,Y]}Z-\nabla_Y([X,Z])
$$
$$=R(X,Y)Z+[X,\nabla_YZ]-\nabla_X\nabla_YZ+\nabla_Y\nabla_XZ-\nabla_Y([X,Z])$$
$$=R(X,Y)Z+\nabla_Y(T(X,Z))-T(X,\nabla_YZ)-\nabla_{\nabla_YZ}X+\nabla_Y\nabla_ZX$$
$$=R(X,Y)Z+\nabla_Y(T(X,Z))-T(X,\nabla_YZ)-\nabla^2_{Y,Z}X$$
where $R(X,Y)Z=\nabla_X\nabla_YZ-\nabla_Y\nabla_XZ-\nabla_{[X,Y]}Z$ is the contracted Riemann curvature tensor, $T(X,Y)=\nabla_{X}Y-\nabla_{Y}X-[X,Y]$ is the torsion, and $\nabla^2_{Y,Z}$ is the second covariant derivative.
If the connection is torsion-free, then this simplifies to $R(X,Y)Z-\nabla^2_{Y,Z}X$.
