What method(s) have proved most successful for you?
Plain and simple, I became fluent in Perl only by hanging out on Perlmonks for a few years. I thought I knew my stuff before I came here, but I was in for quite an eye-opener. I don't think any other approach could have been nearly as effective, at least for me. I have a few Perl books but I never really looked at them -- the monastery and perldoc have everything I might ever need.
I learned algorithms and other useful programming paradigms (e.g, functional programming, recursion) from years and years of university classes. This high-level stuff can apply to any language, and is just as important as knowing a language well enough to apply it effectively. It took a lot more time to become really comfortable in the computer science, compared to the programming. I feel like I have all the programming skills I will ever need, but I can never learn enough computer science.