I asked this Quora question when I arrived in China and was struggling to learn Chinese. I've recently turned the corner and can now have day-to-day life conversations with Chinese people. Although I'm nowhere near the level of proficiency I desire, I have found a process that is working for me and feel bit more qualified to answer my own question.
I moved to China in the Spring of 2012. It was a hard landing for me, much harder than I expected. In America I spent about 6 months studying part time with software products like Memrise, Chinesepod, and Anki flashcards as well periodic lessons with 1-1 tutors. I continued this practice in China, and by May of 2012 I was intensely frustrated with my progress. Chinese people had a hard time understanding even basic words I was saying and I understand almost nothing of what I heard. Fortunately my hours using Memrise had given me a good grasp of pinyin and knowledge of about 1,000 characters, so at least I could use SMS to communicate as a last resort. But overall I realized that if I didn't find a better approach to start rapidly improving I was on the road to becoming another Westerner who tried to learn and gave up.
Out of sheer frustration I started reaching out to people like Daniel Tedesco (see his answer) and others for advice. I took Benny Lewis ("fluent in 3 months") to dinner and got his advice. I was shocked at the wide range of opinions, some strongly held. Some of the advice was helpful, some (like "just get a Chinese girlfriend") was useless to happily married me.
I met a lot of Westerners who started working when the first arrived in China, took few hours each week of lessons, and never really got to the point where they could use Chinese as well as I can now. I commonly hear the regret, "I wish I had first focused on Chinese when I arrived."
Every Westerner I met who was "fluent" (1) spent at least several months studying Chinese full time, and (2) spent massive amounts of time speaking 1-1 with native Chinese people.
Of course this doesn't mean that software products, classrooms, and studying part time don't help - I just didn't meet anyone who had used them successfully.
So in early June I decided to give myself a 3-month deadline of getting to basic efficiency or give up. I stopped taking meetings in Beijing, stopped work on any other projects, and dedicated myself full time, 7 days a week to learning Chinese.
I increased my 1-1 time with Chinese teachers from ~8 hours/week to ~25. I found two great teachers（one from a school in Beijing , one referred by another American expat) and worked with them 1-1 for 3-6 hours per day, 7 days/week. These 3-hour sessions were exhausting at times.
Outside of class I got stacks of spoken Chinese textbooks with MP3 recorders. I spent hour after hour listening to MP3s, reading dialogs, and asking my teachers for help whenever I didn't understand a word or grammar. Whenever I could listed to the MP3 at full speed and read and understand the entire dialog I would move on, never going back, always moving on to the next dialog.
No flashcards, no textbook exercises (unless part of speaking with my teachers).
I started watching episodes of 喜羊羊与灰太狼 per Daniel's advice. I could not (and still can't) follow the dialog at full speed, so my teacher would transcribe the dialog for me and I would study it as well. With my teacher I would explain the entire episode to her, ask questions, and attempt to use the new words and grammar from the episode. When I could watch it at full speed and understand everything I would move on. Sometimes I would have to see the same word multiple times before getting it.
Since I never hand write English, I decided not to learn how to write Hanzi characters except 一 、二、三 :-). But I did type Hanzi everyday, typing out homework assignments, creating my own fictional dialogs, and writing stories. Every day I read them with my teacher, get errors corrected, and talk about them.
I looked for every daily life opportunity to speak Chinese. Before going to get a haircut/buy something/to a restaurant I would write out fictional dialogs about what I planned to do, then I would read and discuss them with my teachers. Then I would go out and use the language in the wild, making mistakes and stumbling through it.
I tried (not always successfully) to not use English. If I took an evening off and watched an English TV program or spoke English with friends I found the next day's class particularly tough. In retrospect, my episodes of progress came when I went into Chinese and never came out for long stretches of time. But it has been very hard and many times I just wanted to quit.
And...it worked. By the end August, my 3 month deadline, I was able to carry out basic life conversations.
I still plan on working 1-1 with teachers a few hours a day, reading Chinese, and writing at every opportunity.
In retrospect, my advice is…
1. If life allows it, dedicate 6 months, full time, 24x7 to studying and using Chinese when you arrive in China. There is so much basic life stuff to organize when you get hear anyway and you can use your time with teachers or students to learn how to use the bank, get a haircut, etc.
2. Find a way to spend 20-30 hours/week in one-on-one dialog with native speakers. Professional teachers are the best if you can afford it ($5-$20 USD/hour) but you can also get students and tutors if necessary.
3. Be patient, be determined. It is so hard but it gets better.