Take sets and functions $s,t:X\to Y$. Let $\sim$ be the equivalence relation generated by the set $R=\{(s(x),t(x)):x\in X\}$. The claim is that the pair $(Y/{\sim},\pi:Y\to Y/{\sim})$ where $\pi$ is the quotient map, is the coequalizer of $s,t$.
To prove this, we need to verify two things:
1) $\pi s=\pi t$
2) if $(C,f:Y\to C)$ is another pair with $fs=ft$, then there is a unique $g:Y/{\sim}\to C$ s.t. $g\pi=f$
For 1): For any $x\in X$, we have $\pi(s(x))=\pi(t(x))$ iff $s(x)\sim t(x)$, by the definition of $\pi$. But we do know that for all $x\in X$, $s(x)\sim t(x)$ (since $R$ contains all pairs $(s(x),t(x))$). Therefore, $\pi s=\pi t$.
For 2): Suppose there is $(C,f)$ as described above. We need to construct $g:Y/{\sim}\to C$. One natural choice would be to define $g([y])=f(y)$ — this will force $g\pi=f$. But I don't see how to prove that the map is well-defined.
Leinster says that the whole thing follows from Remark 5.2.8 (also quoted here), but I don't see how exactly everything follows. The remark says that maps $Y/{\sim}\to C$ correspond bijectively to maps $F:Y\to C$ such that $y\sim y'\implies F(y)=F(y')$.
Best Answer
To show that $g$ is well-defined, notice that $\{(y,z)\in Y\times Y:f(y)=f(z)\}$ is an equivalence relation on $Y$ that includes your $R$ as a subset. So it includes the equivalence relation $\sim$ generated by $R$ (by definition of "generated"). That is, if $y\sim z$ then $f(y)=f(z)$, which is exactly what you need to make $g$ well-defined.