Practice!

Coding in an interview is unlike any kind of programming you have probably done so it's only natural to freak out a little. Personally the whole exercise of writing code not on a computer is bizarre enough on its own!

Find some problems that you might expect to be asked and then actually code them up on a white board or at least with a pen and paper. Bonus points for getting a friend to ask you questions.

here's a nice looooong blog post basically saying the same thing: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog...