There are a lot of good answers here already, but let me throw my 2 cents in...
I have been using photoshop since the 1st version and have read a lot of books on it and keep several for reference...
Considering the fact that your just getting into photoshop I would recommend Adobes' 'Photoshop, classroom in a book' first... It pretty much shows you what the program is comprised of, what all the tools do, where to find things in the menus...
Once you have a good grasp of the programs basic functionality I would recommend the 'photoshop bible' for reference and a few tips and tricks... this is a pretty good book because it touches all the bases...
Deke McMlelland is essentially the go-to photoshop guru for taking photoshop to it's limits and really stretching the functionality, but while as someone new to photoshop you would be able to follow what he is saying he rarely touches on the basics... I would hold off on getting Dekes books til after you get the basics down... I have nothing against Deke but he might not be the best for a beginner, for example some tools and filters in photoshop are capable of creating multitudes of effects beyond what they were designed for and by solely following Deke you may not ever get the basic functions of the tools and filters...
The way I went about learning photoshop is probably different than most, I started using photoshop with the first version... I kind of grew with the program and learned the functionality of the tools as they were released with each new version... but I would recommend starting with learning the basics because in photoshop even the basic tools and functions are powerful and can accomplish most of your goals... And then once you've got a grasp on that look up things as you have a need for them in other resources...
As for what version to buy... anything version 7 and up is probably going to be fine and cs3 or 4 if money isn't an issue...
have fun using PS and stay safe out there!