Since I'm soon going to China for vacation, I thought I should at least learn the basics before I arrive. Being familiar with Kanji helps immensely with recognizing Hanzi (the original Chinese characters) - many are identical, even have very similar readings. Only "simplified" Chinese is a bit tricky, the characters don't really resemble Japanese.
Aside from the characters, Chinese has an additional difficulty: tones. The difference between mā (mother) and mǎ (horse) is just the direction of your voice (flat vs fall-rise). But wait, there's more. In addition to tones, Chinese has consonants that are quite hard to distinguish for us: jī vs qī or xuān vs shuān.
The best way I've found to deal with this so far is [cached]Chinese Pinyin Trainer, a cheap Android app that quizzes you on minimal pairs that only differ in tone or consonant.
A [cached]phonetic table can also be extremely helpful if you want to play around with sounds and train yourself to hear the difference.