To learn Spanish, you’re going need a way to learn correct pronunciation, a frequency dictionary to form your base vocabulary, and a good grammar book.  You’ll also benefit from a thematic vocabulary book for specialized vocabulary and maybe a book or two, once you learn your first 1000 words.  Make sure you read the Method sections of the website, then check out some of these recommended resources (pictures are links):

Pronunciation

First off, get a feel for how pronunciation works in English.  The video tutorials here should help.

Once you understand that, start working on Spanish. The Pronounce it Perfectly series comes with Audio CDs, all the pronunciation rules, and I’ve yet to see one that wasn’t excellent.

If you want to jump to free internet resources, check out the Spanish Pronunciation Wikibook, Wikipedia’s Spanish Phonology page and StudySpanish.com’s pronunciation guide with recordings.

If you’re a native English speaker, you’ll need to learn to hear and pronounce these consonants:
β (bebé), ɣ (trigo), ʝ (ayuno), x (jamón), ʎ (pollo), ɲ (cabaña), r (carro), and ɾ (caro).

You’ll have a pretty easy time with the vowels. There are basically only 5 of them: a (azahar), e  (vehemente), i (dimitir), o (boscoso), u (cucurucho). You’ll need to get rid of your English diphthongs for “o” and “e” (we don’t really say “o”; we go “oh-uu”), and you’ll need a brighter “a.” I talk about all threeof thesethings in the French vowel video, so just watch that and ignore the blabbering about nasal vowels, since you don’t need those.

All of the other sounds in the language should be familiar to your ears and your mouth.

Your base vocabulary

I’ve made a base vocabulary list of 400 words to start you off! As I talk about in that article, I find it easiest to translate those words using the short dictionaries at the end of a Lonely Planet Phrasebook; they’re cheap, short and give you good, standard translations for your words (just ignore the ridiculous pronunciation guides). Later, when you’re ready for sentences, you can go back to your phrasebook and grab some.  After that, try some of these resources:

The Routledge Frequency dictionary series is excellent, with example uses and everything.  Get this at the beginning to direct your vocabulary work!
The Mastering Vocabulary series is a wonderful set of books that contain core vocab for just about any field/topic you can think of.  They’re great for adding to your vocab once you get your first 1000 or 2000 words from a frequency list.
In terms of free resources, Wordsgalore has a decent list with translations of the top 1000 with mp3 recordings.  They’re not in frequency order, but that’s not a big deal; you should know at least the top 1000 anyways.

Grammar book

There are a lot of options here; so far, my pick would be Practical Spanish Grammar.

Book-type book

You can read anything that you enjoy.  I’m a big fan of the Harry Potter series in translation, especially if you can find an audiobook version to listen to at the same time as reading.

Other Resources

Typing

You’ll need to be able to type a few new characters (á, é, í, ó, ú, ü, ñ, ¿ and ¡). There’s a great, straightforward article on this at Spanishdict.com, with instructions for Macs and PCs.

Monolingual Dictionary

Once you learn enough Spanish, move to a monolingual dictionary.  RAE’s Diccionario de la Lengua Española is free and excellent.

Linguee is a lovely dictionary resource, in that it shows you multiple example sentences for each word and tells you about each word’s relative frequency in the language. (Currently in English, Spanish, German, French and Portuguese)

Assimil

The Assimil series is a sort of special language learning resource that I discuss in a blog post here.  It doesn’t quite fit into any of the categories above, and I think it works best as a sort of supplemental source of Spanish input.  Here’s the beginner Spanish version with CDs.

Speaking Practice

Spanish Language Immersion Programs

There is a tremendous thread about immersion programs in Latin America up at Reddit. Check that out. The first suggestion is pretty awesome, at $750 for an entire month of private lessons and lodging in Costa Rica.

Also this program in Peru is pretty neat. They’re an NGO that teach single mothers how to be Spanish teachers. In general, you’re looking at ~$7.50-9.50/hour for private classes, $90/week for homestays (food included), which works out to around $1000/month for 20 hours of weekly private classes, food and lodging. (See this post for details)

Also check out the Escuelas Oficiales de Idiomas in Spain. Every little community has its own and they’re public (i.e., cheap). Eventually, it’d be nice to have reviews of each little school. If you’ve been to one (or know someone who has), let me know and I’ll add it here!