I recommend a combination of traditional text book learning and immersion. The text book tuff is essential for the more technical side of the language (how a setence is set up, the various rules for conjugation, the different tenses, etc.). Immersion will help with your vocabulary and help to make your speaking style more natural. You can't do one or the other, you've got to do both.
The good news is that Spanish is a very logical language. The rules make sense, and in most cases there aren't many exceptions (and the exceptions are exceptions for a reason). It gets to a point where you can know most conjugations just with a good idea of the rules and why exceptions are made. Just to give you an example, each letter has one and only one pronunciation. You know how to pronounce any word just by seeing it.