First off, adults learn languages differently than children. Our brains are less flexible, but we have more powerful conceptual tools that we can use. That means that where a kid can soak up a new language like a sponge, simply through intuition and by being exposed to it, an adult has to work at it.
However, an adult can learn a new language just about as quickly as a child -- even if s/he won't be able to reach as high a level of fluency in it.
But... memorization, drill, and rote practice are pretty much unavoidable, if you're an adult that is. At least to some extent.
What environment works best? In my experience... it doesn't really matter. If you're motivated, any environment will work; if you're not, you won't learn even with the best teacher and the most supportive environment in the world.
The advantage with structured environments like classes is that if you're *kiinda* motivated but not really passionately interested (or forced to), it gives you that little extra push that you might need. But if you have the motivation and self-discipline, you'll learn the basics from language tapes just as well. But motivation is the key -- if you're ready to do the work yourself, language tapes are fine; if you're not quite sure, classes help a lot. Bricks and mortar and classmates are likely to be more motivational than online classes.
As to German, it's not particularly hard for an English-speaker: there's a pretty big base of shared vocabulary, and the grammatical structure will be vaguely familiar. However, it's a great deal more complex grammatically, with three genders, several noun and adjective declinations, sentence structures with semantic differences, and quite involved verbs. The nice thing is that it's very systematic and logical, with a good deal fewer exceptions and general randomness than, say, French or English. (Big surprise there, I'm sure.)
Okay, so how do you go about learning a new language? Lots of ways, I'm sure, but here's what works for me:
Phase 1: The basics.
This is the least fun bit. It means drilling in the basic grammar and vocabulary. That means rote memorization of words and phrases, pronunciation, and grammar drills. You can learn this in class or from language tapes. Don't expect it to be a lot of fun, especially if you don't enjoy memorization. There are supposedly less painful ways of doing this, but IMO they aren't really, and will just take longer and leave you with a mushier base to build on.
At the end of this phase, you should have basic "tourist level" language skills, and be able to understand the headlines in a newspaper, and have a general idea of what the article is about, even if you won't be able to follow a conversation or read a book. If you practice intensively, it'll take you a few weeks to a few months, depending on how quick and especially how motivated you are.
With Russian, I did this at university -- I took a few levels of Russian one after the other, starting with reading comprehension and going on to general language courses.
Phase 2: Expansion.
Now, this is where you're kinda stuck if you're all alone. You really need someone to practice on/with. Conversation classes are great. German e-mail pals are great, if you want to focus on written rather than spoken German. You might want to try reading German magazines or, for example, websites (but forget forums like this one; the slang will be way beyond you).
Another tip: music. I got through this phase in Russian in two stages, the first of which involved discovering Russian songs. I built up a small collection of CD's from bands like Akvarium, DDT, Krematorii, Nautilus Pompilius, and so on, and got hold of the lyrics. I then deciphered the lyrics with a dictionary. Because it's music, it's easy to memorize, and I managed to build up a quite a bit of vocabulary in a way that was actually fun, and it strengthened the "feel" of how the language works. Reading poetry out loud does the same thing.
Oh, the second phase? I enrolled in a summer class in St. Petersburg. Spent a month going to Russian classes there (and of course had to survive in the Russian-speaking environment).
Phase 3: Use.
OK, at this point you'll have a pretty good feel for how the language works, and have enough core vocabulary that you'll be able to read a magazine with the help of a dictionary. Or carry on a conversation if your interlocutor is a bit patient. Here, it all depends on you and your priorities: spoken or written, prose or poetry, fiction or non-fiction, conversation or public speaking, and so on. The main thing is that you do something to *use* that language.
I did this stage of my Russian-learning by going to Ukraine for a year.
PS. Good pick. If I had to pick my languages all over again, German would get a much higher priority than it did. Germans are super-nice, and their press and literature are among the most varied and best in the world.