Dating someone who speaks the language (before, as well as while you are there) is also very, very helpful. (I didn't do this in China, but my friends who did definitely had a leg up).
If you do this, beware that some languages are enough different for male and female speakers that you may end up learning lots of gender-confusing idioms. I've read that English-speaking men in Japan sometimes end up speaking fairly fluent "Japanese girlfriend" rather than the Japanese they'd be speaking if they'd mimicked other males.
