I had both Malayalam and Tamil speaking colleagues and we often discussed languages. As a non speaker of either, they sounded exactly the same but with different accents, so I often asked a lot of questions. My answer is from what I have observed, not from a research paper of an Indologist (neither am I a linguist).
They are to a large extent, having more mutual intelligibility than other (major) South Indian languages. They even have quite similar phonology that sounds odd to other South Indians(mainly usage of voiced and unvoiced consonants). Linguists believe that Malayalam evolved from Tamil fairly late, between 800 AD and 1300 AD, though not all Malayalam speakers agree with that - some claim it is much more ancient than that and some even go to the extent of claiming that Tamil Sangam literature was written in Old Malayalam, not Old Tamil. It isn't uncommon for Malayalam speakers and Tamil speakers to speak in their respective languages and have a conversation if one of them doesn't know English. However, a few factors hinder such a conversation from being smooth and flawless.
Malayalam speakers are notorious for their accent - they are perceived to speak faster than others - so it is hard to decipher them. Some words are unique to each language, and a few common words have quite different meanings (e.g. 'patti' (t - retroflex, a,i -short, p - unaspirated) means dog in Malayalam but village in Tamil). Malayalam has more Sanskrit loanwords than Tamil, and has borrowed with little morphological change compared to Tamil (other language speakers who have no clue of Malayalam can easily get gist of what is being said by their knowledge of Sanskrit owing to their own borrowings, if they can decipher the accent that is). This might cause a problem in picking up words. Further, although Sanakrit loanwords are found in all Indian languages (except probably north eastern ones which aren't Indo-European or Dravidian, except Assamese and Bengali), not all borrowed words have same meanings. The change ranges from subtle variation in meaning to downright opposite or contradictory(e.g. 'garva' in Hindi means pride in a positive sense but in Kannada means pride with severe negative connotations - its one of the trigger words in Kannada). So a Sanskrit origin word needn't always mean the same, and it is often best to ask when a word seems out of place in the sentence.
EDIT:
This answer has been getting quite a bit of attention every now and then, and I thought of adding some reference to demonstrate the mutual intelligibility. In this video Vidya Balan, a popular actress in India, is interviewed in Malayalam but she responds in Tamil, yet the interview goes on smoothly. At 11:28 they talk about her command of Malayalam, or lack there of. At 12:20 they both acknowledge Vidya has been speaking in a dialect of Tamil.
Disclaimer: I don't know if this was for a TV channel and if subtitles were used, which I seriously doubt. The interviewer might have been bilingual too.
https://www.youtube.com/watch?v=p8aJpq9j4ms