Okay, first of all you could read something about the Chinese language on wikipedia.com. Just a short background will help you to understand some stuff. Like, do you want to learn the traditional characters or the simplified ones? (I'd go for the Simplified ones, which are used in Mainland China. Unless you are really interested in Taiwan of course, because they still use traditional ones there.) Then you could look for some free material. www.chinesepod.com has some great podcasts and a free pinyin chart with the pronunciation of every possible combination and tone. Next I'd suggest picking up a book with tapes/cds. (E.g. Colloquial Chinese by Kan Qian) Oh, and you could try finding some HSK-vocabulary lists.
I wouldn't necessarily advise against just talking with natives, but it's just different over the internet with someone who isn't really a teacher. Of course you can learn some stuff, but it's better to build up some knowledge first so that you can actually learn something from your language partner. (Otherwise the conversation will always go slow and eventually you'll just be speaking English again.)
Good luck! 祝你好运！