This has become a response of some length, so I'll put a quick summary up front:

- From the perspective of linguistics, a "language" and a "dialect" are essentially the same thing; which word is used is a political question, not a scientific one.

- One common method of assigning different meanings to "language" vs "dialect" is to say that if person A and person B can communicate using A-speak and B-speak, then A-speak and B-speak are both dialects of the same language. On this approach, Mandarin and Cantonese are separate languages, and e.g. Beijinghua is a dialect of Mandarin.

---------

I understand that Mandarin, Minnan, Wu, Yue, etc etc etc aren't all the same thing. That wasn't what I meant. If the question is "are Mandarin and Cantonese the same language?", it's easy to demonstrate, e.g. by having two people attempt to communicate, that they aren't.

Consider an alternative question, "are Mandarin Chinese and my quilt the same thing?" It should be clear that they aren't. Furthermore, they aren't even the same kind of thing -- one is a quilt, and one is, in the context of comparing it to a quilt, clearly a language. We can distinguish the language from the quilt by many tests: one has a physical instantiation (the quilt), and from that many ancillary properties like color, weight, size, rigidity, and so forth; the language is more of a hypothetical concept with no physical object that represents it, but can be conceived of as a tool for communication much as the quilt is a tool for keeping warm. All normal humans over the age of four "possess" one or more languages; many lack quilts.

So, if we keep the question "is this thing that I'm considering a language, or not?" in our minds... the point of my earlier rhetorical question is that there is no distinction to be drawn between Cantonese and Mandarin that would be relevant to that question. Any evidence you adduce to support the idea that Mandarin is a language will apply just as well to Cantonese, and vice versa.

> But then how would you explain the relationship between Chinese, Mandarin, Hokkien, Hakka, Teochew, etc in terms of language vs. dialect?

"Dialect", like "species", is not a perfectly well-defined concept. Some people (not me) like the ecological species concept (which I will rudely characterize as "two animals are the same species if an ecologist tells you so"), and some (most) prefer the biological species concept, which says that two animals are the same species if they can mate and produce viable, fertile offspring (as far as I can tell, the requirement of a single generation of fertility is there specifically to stop donkeys and horses from being the same species under this concept; the occasional fertile mule is handled by the traditional fingers-in-the-ears method).

Analogously, it's common to say that two, um, "modes of speaking" A and B are dialects of the same language if a person speaking A can carry on a conversation with a partner speaking B. By this view, a "language" is a very abstract concept, less physically real than a "dialect" in the same way that a dialect is less physically real than a quilt. The way any person speaks, which though massless is something you can measure in the world, is a dialect, and a language is a group of dialects which are all mutually intelligible.

Like the biological species concept, this has some issues; for example, it tends to suggest that Spanish and Italian are dialects of the same language. This is felt to be politically unfortunate, but from a facts-based perspective things could be a lot worse -- Spanish and Italian are known to be closely related, both recent descendants of Latin.

So to answer your question:

"Chinese" is a term with no clear meaning, usually synonymous with Mandarin. The structure of the word indicates that it refers to the language of China, but as there's more than one that's not very useful. Mandarin, Yue, Wu, Min, Hakka and so on are all "languages" (or "language families"), and Shanghaihua is a dialect of Wu, Beijinghua is a dialect of Mandarin, Guangdonghua is a dialect of Yue, etc. You can read more here: http://en.wikipedia.org/wiki/Varieties_of_Chinese

All of these language families share an obvious (well, depending on your perspective) similarity because they descend from Middle Chinese, just as French and Italian share similarity because of their common descent from Latin.