Practice. I bought a whiteboard, mounted it on the wall, and practice questions from interviewcake as if I were in front of a live audience. It feels kind of silly, but definitely helped me improve recall under the pressure of an interview. Putting yourself in an environment that most closely resembles the stress of the real thing to induce some or all of the anxiety is paramount!

Repeating this exercise at least once daily has produced real results for me, and helped me get comfortable thinking and speaking about algorithms outside of my normal operating environment (i.e. in front of a keyboard ;).