Strange, I could swear I replied to this yesterday. Anyway...
I'd say the best way to learn at least the basics is to pick up one of a couple of books. The book I have that I would recommend is the Classroom in a Book series. They consist of tutorial projects that walk you through how to do most of the basic stuff that AE can do. Once you've learned how to use AE keyframes and the basic controls, it should be easy enough to figure out most of the effects that aren't covered by trial and error (I don't know about the new version of the CinaB, but mine does cover a lot of text effects). Another book I've heard is good is the After Effects Bible. I'm hoping for this for Christmas.
Amazon has both of these books, and you might be able to find them at half.com for even cheaper. I picked up an older version of the CinaB for AE for less than $10 at half.com, and it's worked just fine for the newer version I've got (not all that much has changed, interface wise).