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.
