I studied 2 years in the US and then spent a semester in China. After 3 years I had a pretty good handle on it.
TIPS:
1. Hang out on chinese-forums.com. Excellent threads about learning, grammar questions, cultural questions, etc. Zhongwen.com is a great starting online dictionary.
2. DO learn to read/write Chinese characters. I never understood how people think they can just get by speaking, the characters help reinforce a lot of stuff and they are easiest to practice without speaking buddies.
3. I would try to learn traditional characters (at least the most basic 1000) and learn simplified in parallel. It is easy and clear to jump from traditional to simplified but not vice versa. Most stuff in Chinese communities in the US (though this is rapidly changing) is in traditional characters.
4. Practice characters
every day. I tried to learn 2-3 new ones every day by writing them 3 lines (on paper) the first day, two the second, and one the third. This helped me get a lot down over time.
5. Learn the radicals first and make sure you get stroke order down well. There are some
animated gifs that are pretty good.
6. If there is a beginning Chinese course on nights/weekends at the local community college or a private language school, I would advise taking it for at least two sessions. The first 6 months of Chinese can be bewildering and there are certain things, like the four tones in speaking, you need a native speaker to make sure you learn right or you will pick up bad habits that are hard to break. They can give you a legit Chinese name (ask for a 3 character last name+ 2 first name) too.
7. Try to get opportunities to speak outside of class. This can be ordering at restaurants or (if you have the money) Skype sessions through eChineselearning.com. I studied 2 years and when I got to China I could not understand or be understood for about a month (though I could read great). Speaking Chinese can't be mastered with audio tapes, Rosetta stone, etc.
8. Get a good Chinese-English dictionary
9. Don't neglect Chinese history and culture--it is very entwined with the language. A good starting book on ancient Chinese history is
The Ageless Chinese by Dun Li. Out of print but you can find on Alibris or in the library. Also learn about modern history (20th century) and the various festivals (Chinese New Year/Spring Festival, Mid-Autumn Festival etc.) Finally some major books like Romance of the Three Kingdoms (in English) are good but are long. Know the characters from
Journey to the West they pop up everywhere.
10. Try to visit China or Taiwan for an extended period if you really want to be fluent. I was lucky in that I took the HSK (Chinese TOEFL) and got a good score and scholarship from the Chinese government to study for a semester. It came right when I got laid off from my job so was perfect timing. You should try to enroll in a university program while you are there are speak as little English as possible.
Finally, don't believe dudes that say getting a Chinese girlfriend will help you learn faster. I knew a lot of dudes who did this from the get go and the never progressed. The girl spoke English well and they resented her always correcting their bad Chinese so they eventually gave up since the difficulty was not helping the relationship. This was even true for people living in China. Every fluent Chinese person I know with a Chinese girl/spouse ironically met them after their Chinese was pretty fluent.