Classroom in a book (CIAB) has a good reputation.
As others have said, the Premiere Pro CS5 Classroom in a Book is quite good.
In November, a training DVD by Jan Ozer and Maxim Jago is coming out: Premiere Pro CS5: Learn By Video. I can vouch for that DVD. (Full disclosure: I did the After Effects CS5 DVD in that series, and a few of my general video concepts videos are also on the Premiere Pro DVD, so I may be biased.)
Your cheapest solution for learning how the software works is by reading the included manual/Help file. Be sure to go in sequence, trying each new concept as you learn it, and looking up the definition for any words you don't fully understand.
Europe, Middle East and Africa