They are:
\begin{align} \cos(a)\cos(b)&=\frac{1}{2}\Big(\cos(a+b)+\cos(a-b)\Big) \\[2ex] \sin(a)\sin(b)&=\frac{1}{2}\Big(\cos(a-b)-\cos(a+b)\Big) \\[2ex] \sin(a)\cos(b)&=\frac{1}{2}\Big(\sin(a+b)+\sin(a-b)\Big) \\[2ex] \cos(a)\sin(b)&=\frac{1}{2}\Big(\sin(a+b)-\sin(a-b)\Big) \\[2ex] \cos(a)+\cos(b)&=2\cos\left(\frac{a+b}{2}\right)\cos\left(\frac{a-b}{2}\right) \\[3ex] \cos(a)-\cos(b)&=-2\sin\left(\frac{a+b}{2}\right)\sin\left(\frac{a-b}{2}\right) \\[3ex] \sin(a)+\sin(b)&=2\sin\left(\frac{a+b}{2}\right)\cos\left(\frac{a-b}{2}\right) \\[3ex] \sin(a)-\sin(b)&=2\cos\left(\frac{a+b}{2}\right)\sin\left(\frac{a-b}{2}\right) \end{align}
I have found nice mnemonics that helped me to remember the reduction formulae and others but I can't find a simple relationship between the formulas above. Can you help?
The only ones you need to know are the classical $\sin(a+b) = \sin(a)\cos(b)+\cos(a)\sin(b)$ and $\cos(a+b)=\cos(a)\cos(b)-\sin(a)\sin(b)$. The others are mere consequences of those.
For example, by changing the signs, you get $\cos(a-b)=\cos(a)\cos(b)+\sin(a)\sin(b)$. By summing, you have $\cos(a+b)+\cos(a-b) = 2\cos(a)\cos(b)$, which is your first formula.
Similarly, by solving $p=a+b$ and $q=a-b$, you get the formula $\cos(p)+\cos(q) = 2\cos\left(\dfrac{p+q}{2}\right)\cos\left(\dfrac{p-q}{2}\right)$.