I personally started learning PhotoShop through the book by Scott Kelby called "Photoshop 7 Down & Dirty Tricks" and there is now a CS version available.
CAVEAT
It does NOT give you a detailed rundown of each and every function/key
It does NOT provide you with in-depth analysis of Photoshop CS
What it DOES do is provide a list of tutorials described in detail with full colour step-by-step photos. Tutorials cover a range of subjects such as how to create Apple gel-like buttons, how to create a metal finish, how to apply tattoos on to a persons arm, how to create chrome type effects, mirror effects, how to blend two pictures, how to create a TV lines effect etc. etc.
I loved it because I could get results immediately, which maintained my interest rather than getting bogged down in the detailed minutie of each functions attributes. Also, after you have done a few tutorials you find yourself repeating keystrokes etc. and through this process you begin to develop an understanding of how each function works.
Of course you will also need a good Photoshop manual to go alongside this, such as the "Bible" series & there are also a whole host of great photoshop resources available on the net.
However I found Scott Kelby's approach really suited my needs and got me off the ground very quickly and I still refer back to it now and again when I need a quick reminder how to do something.
Vanilla