Coming in late to the Xiao Hu/pefferie debate, and on the matter of character-learning methods, I cast a vote in favor of "everybody." People learn in different ways, and it's important to find a way that works for you.

Adding to what Xiao Hu and pefferie have already said:

Mnemonics seem to be one of those things that either work wonders or don't work at all. In my experience, they don't scale very well beyond the first few dozen characters, but it's entirely possible that I've been doing it wrong. Flashcards are also something that i never used much, but that's probably due to my own laziness more than anything else. The bad news about characters is that it will be kind of a slog when you start out no matter what; the good news is that it gets a lot easier once you have a hundred or so characters under your belt, because you'll be able to learn new characters by relating them to old ones -- 最 is just a 日 plus a 取, and hey, that 取 is an 耳 plus a 又. Some of these character components are radicals; others are a semi-helpful clue to the sound (工 rhymes with 空); others are just components ("primitives") that get reused a lot.

Reading and writing are kind of separate skills when it comes to Chinese. The best way I've found for learning to write characters by hand is just to write them by hand -- again and again. And again. Write a new character ten times and you've got it on loan; 20 times and it's yours. If you've got access to a Chinatown with a bookstore, you might want to look for 字帖 zìtiě -- children's character-tracing workbooks, which come handily pre-printed. The good news is that you can do a lot of this while doing other things -- watching TV, say.

As for the Simplified/Traditional debate: it depends on where you are and what you want to do -- the PRC uses simplified characters; overseas communities in the US tend to use traditional, though this is changing -- but the short answer is probably "Simplified." The longer answer is that it doesn't really matter: as Xiao Hu notes, there's a lot of overlap between the two systems, and even things that don't overlap 100% will still be pretty close most of the time -- 话 is 話; 語 is 语, and so on. Pick whichever one you like, and after a while you'll realize that you can read the other one without too much difficulty.

For speaking practice: talk to yourself. Try to narrate whatever you're doing in Chinese -- even just in simple sentences. This will feel weird at first, but it's a good way of getting yourself used to thinking in and "speaking" the language. Once you get confident doing this and you're able to form longer sentences, push yourself a bit farther -- record an audio diary every night describing what you did that day. Listening to yourself speaking a second language is painful, but it's a great way to catch yourself making mistakes so that you can fix them.

You mentioned watching Chinese movies -- this is going to be a GREAT way to practice listening once you've gotten a bit further.

Find a DVD of something you'll want to watch multiple times. First, watch it with the Mandarin soundtrack and English subtitles. Then watch it with the Mandarin soundtrack and Chinese subtitles. Even if you're only recognizing one character out of three, the Chinese subtitles will help remind you of what people are saying -- and you'll already have an idea of this from the first time you watched it, so you won't be too lost. Finally, watch the movie with no subtitles. You won't have to strain to follow the plot, so you'll be able to just relax and let the dialogue wash over you, picking out a word here, a phrase there, and eventually whole sentences.

Hope this helps -- good luck, and welcome!