Start off by reading Typography for Lawyers and iA’s post “Web Design is 95% Typography”. Both links have great advice and talk about the fundamentals of typography and type on the web.
If the last links perked your interest than I recommend picking up The Elements of Typographic style. It is a great bible on the subject at the macro level.
[1]http://www.typographyforlawyers.com/
[2]http://informationarchitects.jp/the-web-is-all-about-typogra...
[3]http://www.amazon.ca/Elements-Typographic-Style-Robert-Bring...
Then once you know what exactly you like and don't like, make stuff.
I think that the first step. Specifics are great too, eswat's recommendation, try to get your hands on Bringhurst's The Elements of Typographic Style. It is the bible for everything type, and is really well written.
Just look at the reading lists from design classes. You'll find introductory texts new and old, like "Design Basics, 7th ed." and "The Art of Color and Design (1951)," but they'll all cover the same things: line, direction, shape, size, texture, value, color, repetition, alternation, harmony, gradation, contrast, dominance, unity, balance, proportion. Take the class and you'll do exercises that let you practice each one, or you can find workbooks related to those textbooks.
Learn layout and composition. "Editing by Design" is a classic. Lay out text and design elements on paper (always Linux compatible). Cartography is also good: it's information design and layout and presentation and art all together.
Learn copywriting. Writing is design: the right word can explain a concept better than a big, shiny icon ever could.
Good web design is good design first, with accommodations made for low-resolution text, small viewports, backlighting, scrolling and pointers. Just as with programming, you can't learn it just by reading about it: you have to practice it.
If you're in Austin, TX, come out to a design workshop. I hold them every other week and we practice various elements of design (using the term broadly): http://vi.to/workshop/
If you're not, maybe there's something similar in your area.
( All suggestions stolen from a previous comment I made: http://news.ycombinator.com/item?id=1290485 )
I am aware that practice is going to be a key ingredient in getting a solid base, but knowing where to begin is often half the battle. Obviously with something as timeless as design, there are a lot of classics out there, but with emerging markets such as netbooks and mobile devices, some new approaches may have merit.
From your and other peoples' comments so far, a good starting point seems to be to dig into some of the classic literature (pretty obvious in hindsight heh). That should start taking care of my theoretical knowledge.
Apart from that, I think your suggestion of just doing layout and design on paper is really great. That will enable me to get a ton of practice without being roadblocked by my lack of experience with graphical tools. I suppose doing quick sketches on paper and then working from there is a pretty standard modus operandi for designers, but for some reason that wasn't obvious to me.