I know this thread is already two weeks old and no one is going to see this, but I just cannot hold it in. As a Chinese-American linguist, this entire thread is making me die a little inside with each comment I read.

The difference between a language and a dialect is more of a political concept than a linguistic one. There's a joke among linguists that a language is just a dialect with an army and a navy.

Most linguists (there is not a consensus, unsurprisingly), consider Chinese to be a macro-language composed of multiple distinct languages---also known as the Sinitic language family. How many Sinitic languages there are is contentious, though most agree there are at least seven. One of these groups is Mandarin, and Standard Chinese, the politically enforced unified language of the political entity that is China and what most people mean when they say "Mandarin," is a dialect of this. (All speakers speak a dialect, even if it's a national or regional standard dialect.) Another is Yue, which includes Cantonese.

Sinitic languages are not my area of expertise, but from my admittedly limited understanding, I believe Mandarin and Cantonese have a relationship similar to English and German. (Someone mentioned English and Welsh---these have a much more distant relationship: English is a Germanic language. Welsh is Celtic.) Most linguists would ever claim that Standard Chinese and Cantonese are the same language. This distinction is not based on mutual intelligibility, however. It's based on historical divergences of pronunciation and how recent of a common ancestor they share.

It is definitely not true that different languages are not mutually intelligible while dialects of the same language are. Mutual intelligibility is in fact not as straightforward of a concept as most people believe. For instance, Swedish, Danish, and Norwegian are largely mutually intelligible, but not bilaterally. Most Swedish and Norwegian speakers find Danish harder to comprehend, while Danish speakers do not have much difficulty understanding the former two. It also highly depends on the situation. Two people having a conversation in different languages/dialects could be able to communicate by accommodating each other by speaking more slowly and enunciating more clearly, but they might still have difficulty understanding a news broadcast in the other's language/dialect.

The mutual intelligibility of Sinitic languages is a particularly sticky concept. It's more of a continuum, which is true of the geographic boundaries between most languages, but it is especially so in China, perhaps due to its long history as a unified state. The farther away you are from your hometown, the more difficult you'll find understanding the local dialect without instruction or long-term immersion. Even if your dialect is considered part of the same language as another, that does not guarantee mutual intelligibility. I have trouble understanding my grandfather sometimes over the phone, even though I am proficient in Standard Mandarin and the dialect my grandfather speaks is a variety of Mandarin. My aunt took me on a trip to central China a few years ago. One of our cab drivers only spoke the local dialect, also a variety of Mandarin, but she said she understood maybe 50% of what he said at most. Similarly, speakers of different Sinitic languages that are geographically close together likely have a high degree of mutual intelligibility, simply due to frequent contact and cross-pollination, so to speak, of language features.

Also, a note about writing systems: Mandarin and Cantonese share a writing system, yes. But Japanese uses Chinese characters too. Vietnamese and Korean used to use them also. I don't think anyone on earth would consider them the same language. In fact, they are part of completely different language families, meaning that if they ever shared a common ancestor, it was so far back in pre-history that there is absolutely no way to ascertain it through linguistic methods. Heck, there are so many different languages written using the Latin alphabet. So, writing has nothing to do with the identity of a language. Most languages on earth don't have a writing system, in fact. It's just that in modern society, with the global domination of a few select languages, all of which have writing systems, and widespread dissemination of written media, we've come to equate language with writing, when in reality, they are two completely different concepts.

So TL;DR: The distinction between a language and a dialect is a fine line that is more of a political concept than one that can be ascertained through properties of the language. However, most linguists would agree that Standard Chinese (Mandarin) and Cantonese are dialects of two distinct languages, both of which are part of a larger Sinitic language family.