Well.
Firstly, Mandarin Chinese is no different from any other language, in that language acquisition is best done through immersion. So look for Mandarin television shows, broadcasts, podcasts etc, and listen to them. Find Chinese texts to read, to accustom yourself to Chinese sentence structures and linguistic quirks.
And, if possible, find a Chinese person to practice with. This is important. You can't learn how to swim by reading about it. Similarly, you can't learn how to speak a language without practicing. See if there's a language exchange program near you. Maybe @
Terrik can introduce you to a Chinese girl who's interested in chatting with a handsome foreign guy with bananas for hands.
Also, during the course of interpretation training, we'd do something called "shadowing". Basically, it's listening to something, and then repeating it either simultaneously or consecutively. This isn't just mindlessly parroting it though, instead you're to listen to it, understand it, and then repeat it. Sometimes you'll find yourself naturally paraphrasing it, eg you hear "It's a nice day today" and you end up saying "Today it's a nice day." This training is usually meant for people who want to become interpreters, but it also helps with getting your tongue accustomed to speaking a foreign language.
Now, unlike lots of western languages, Mandarin Chinese is a very tonal language, in that each sound can mean different things depending on whether the tone is ascending, descending, flat, etc. Remember to practice this part, as I find it's one of the things foreign speakers often have trouble with. Additionally, Chinese has a topic-comment sentence structure, which can take getting used to. You'll probably want to watch out for it too.
Sorry I can't be more help, I learned Mandarin Chinese growing up, so I don't really have much experience learning it as a foreign language. Terrik, Timmus, the Khan etc can probably offer more insights in this regard.