How can I understand and prove the "sum and difference formulas" in trigonometry?

Here are my favorite diagrams:

As given, the diagrams put certain restrictions on the angles involved: neither angle, nor their sum, can be larger than 90 degrees; and neither angle, nor their difference, can be negative. The diagrams can be adjusted, however, to push beyond these limits. (See, for instance, this answer.)

Here's a bonus mnemonic cheer (which probably isn't as exciting to read as to hear):

Sine, Cosine, Sign, Cosine, Sine!
Cosine, Cosine, Co-Sign, Sine, Sine!

The first line encapsulates the sine formulas; the second, cosine. Just drop the angles in (in order $\alpha$, $\beta$, $\alpha$, $\beta$ in each line), and know that "Sign" means to use the same sign as in the compound argument ("+" for angle sum, "-" for angle difference), while "Co-Sign" means to use the opposite sign.

The key fact here is that rotation is a linear transformation, e.g. the rotation of $u + v$ is the rotation of $u$ plus the rotation of $v$. You should draw a diagram that shows this carefully if you don't believe it. That means a rotation is determined by what it does to $(1, 0)$ and to $(0, 1)$.

But $(1, 0)$ rotated by $\theta$ degrees counterclockwise is just $(\cos \theta, \sin \theta)$, whereas $(0, 1)$ rotated by $\theta$ degrees counterclockwise is just $(-\sin \theta, \cos \theta)$. (Again, draw a diagram.) That means a rotation by $\theta$ is given by a $2 \times 2$ matrix with those entries. (Matrices don't work here yet.)

So take a rotation by $\theta$ and another one by $\theta'$, and multiply the corresponding matrices. What you get is the sine and cosine angle addition formulas. (The connection to complex numbers is that one can represent complex numbers as $2 \times 2$ real matrices.)

Also, if you believe that $a \cdot b = |a| |b| \cos \theta$, this implies the cosine angle difference formula when $a$ and $b$ are unit vectors. Ditto for the cross product and the sine angle difference formula.

Though the standard high-school derivations are not the most useful way to remember it in the long run, here's another one which I like because you can "see" it directly without much algebra.

Let P be the point on the unit circle got by rotating (1,0) by angle α+β. Drop a perpendicular N to the α-rotated line, and R to the x-axis. So from the right triangle ONP, you see ON = cos β. You can see that the angle RPN is α too: it's the complement of ∠PNQ, and so is ∠QNO = α. Now,

$\sin(\alpha + \beta) = \mbox{PR} = \mbox{PQ} + \mbox{QR} = \sin(\beta)\cos(\alpha) + \cos(\beta)\sin(\alpha)$, and

$\cos(\alpha + \beta) = \mbox{OR} = \mbox{OM} - \mbox{RM} = \cos(\beta)\cos(\alpha) - \sin(\beta)\sin(\alpha)$.