The single most important thing one can do is to have someone who already speaks the language around, so you can practice your new language. More than one person is, of course, better, and actually living somewhere where the new language is the primary language is ideal. Selecting a language that is reasonably similar to a language you already know well (i.e., a Germanic or Romance language if you speak English) will be much easier than a more distantly related language, since words will share common roots, and thus be easier to remember.
Learn how to say, "How do you say ... ?" and "What is this called?" in the new language. Use these phrases early and often. It doesn't matter so much if you actually remember the responses you get, just hear the words. (Having a patient conversation partner helps immensely.) Don't worry about the grammar at first, just memorize the sounds of these two phrases and repeat them by rote.
Learn to count. Learn basic present tense verb conjugations. Talk to yourself in your new language. A lot. Keep a running narrative in your head of things you do.
Write things as often as possible in the new language. Make signs. If you're taking a class, make sure to do all the homework. Write notes and reminders to yourself in the new language.
After you achieve reasonable low-level proficiency, argue with people. You'll surprise yourself with how easily the words come during a heated exchange.
Lather, rinse, repeat.