I'm trying to get my head around the notion of a connection on a ''space'' $X$ over some field $k$. (I am mainly interested in connections in algebraic geometry as they can be used to define the de Rham realisation of the fundamental group, but please feel free to assume $X$ is a complex manifold or some other suitable space as this is about intuition.)
What I have heard about connections is that they ''connect'' the fibres of some bundle $\mathcal{E}$ over $X$ i.e. if $\mathcal{E}$ is a locally free sheaf on $X$ and there is a path $x\to y$ in $X$ between two points then there should be a morphism $\mathcal{E}_x\to\mathcal{E}_y$ of the stalks over these two points (as far as I understand this is parallel transport). This allows us to talk about monodromy representations of the fundamental group of $X$ etc.
But the definition I have read (e.g. in Szamuely's book Galois Groups and Fundamental Groups) is that a connection is a pair $(\mathcal{E},\nabla)$ where $\mathcal{E}$ is locally free over $X$ and $\nabla$ is a morphism of sheaves of $k$-vector spaces
$$\nabla: \mathcal{E}\to\mathcal{E}\otimes_{\mathcal{O}_X} \Omega^1_X$$
satisfying the Leibniz rule $\nabla(f m) = m\otimes df + f \nabla(m)$ for $f$ a section of $\mathcal{O}_X$ and $m$ a section of $\mathcal{E}$.
How are these two notions equivalent, and is there any further intuition about either one?
These two notions are equivalent. If you have connection $$ \nabla: \mathcal{E}\to\mathcal{E}\otimes_{\mathcal{O}_X} \Omega^1_X $$ and choose a path $\gamma(t): I=[0,1] \to X$ in $X$ you can define a parallel transport of a section $s$ of $\mathcal{E}$ as solution of the differential equation $$ \nabla_{\dot \gamma(t)} s (\gamma(t))=0, $$ satisfying initial condition $s(\gamma(0))=s_0$. Here $\nabla_{\dot \gamma(t)}$ is the substitution of the vector field $\dot \gamma$ in the 1-form $\nabla s$.
A 1-form is a section of the cotangent bundle $\Omega$, which is dual to the tangent bundle. You can always compute (or evaluate) section of the dual vector bundle on a section of a bundle and get a function. More generally, if you consider a 1-forms with values in a vector bundle (i.e. $\mathcal{E} \otimes \Omega$) you get a section of this bundle when substitute a vector field in this form.
In the other direction, if you have a notion of the parallel transport along a curve $\gamma$ in $X$ you can move section by some $\epsilon$ and take limit just as for ordinary derivatives, this will define for you $\nabla_{\dot \gamma(t)}$. Then, if you have any vector field $v$ on $X$ find an integral trajectory $\gamma$ of that vector field passing through a given point $x \in X$ $$ \frac{d}{dt} \gamma(t) = v(\gamma(t)) $$ and $\gamma(0)=x$. Use previous step to define $\nabla_{v}s=\nabla_{\dot \gamma(t)} s$. Now you have a map for any vector field on $X$, therefore you obtained a 1-form $\nabla s$ with value in $\mathcal{E}$.