Proven secure, broken anyway

An algorithm can be "proven secure" mathematically and yet be broken in practice by a side-channel attack.

Explain this paradox: what exactly does the mathematical proof guarantee, what does it not cover, and give a concrete example of a leak. What must be done, beyond the choice of algorithm, to be truly secure?