Chessmaster is supposed to have an array of lessons in it. Maybe a recent user can elaborate.
A beginning tactics program might also be in order. When done with that then the intermediate package. Am thinking the Convekta series?
Chess Software for beginners?
Sort:
Well, the more recent Chessmasters have a wide array of lessons - tactics, openings, endgames, essentially everything you need to know for a LONG time. It teaches using diagrams, text, and audio, which makes the material much easier to learn.
Chessmaster, Chess.com's Chess Mentor, or Chesskids.com are great choices. I don't think Fritz fits the bill since it doesn't include so many tutorials and interactive exercises as the other choices--it's more for game analysis. And Convekta's CT-B is more of a tactics workout--maybe better as a follow-up to the other options. My wife actually learned how to play chess using the first and third options and enjoyed the experience. :)
Also note that the Fritz 11 engine can only be adjusted lower to a certain extent, it's still a fairly "strong" engine against a beginner. Chessmaster would be good, but for the money I think a few months of chess mentor is invaluable, it allows you to work on almost any area of the game you want, plus you can easily choose problems of a given difficulty.
I bought a copy of Majestic Chess about a year ago at Staples. It seems like a modern version of Chessmaster 4000. Both programs are very suitable for a beginner with lots of levels. I think Chessmaster 4000 had more adjustable playing styles but Majestic Chess has an adventure game that acts a a tutorial. It starts with basic moves and individual pieces and gradually works up to a full set and game.
Chessmaster 4000 is probably long gone from stores. I think I got it on a promo CD in a magazine about eight years ago. I paid $10.00 for Majestic Chess in a close-out rack but you still might find it somewhere.
Personally, I'm planning to buy the latest Chessmaster soon. On the side I'm starting to tinker with some of the free GUIs and databases out there.
Chessmaster 10th Edition, for Josh Waitkin's Academy Lessons.
Comparing the suggestions and price i went with Chessmaster: Grandmaster edition which includes Josh Waitkin's the art of learning and it was only 20 dollars. Im reserved about subscribing to chess mentor because my wife is in nursing school and I'm afraid i would be paying continually for something she might not be able to use very often. Thanks for the advice I'll let you know how chessmaster works out.
Good choice 
Any thoughts on Chessmaster 10 vs. 11 (Grandmaster edition)?
Yes i have to agree with all the peoples that recomends Chessmaster. I myself use Chessmaster 10 Grandmaster edition(CM11). It got everythink, from basic to advanced. As someone mentioned it has a learning course with Joshua Waitzkin...very good. Both you and your wife should be able to learn and have fun with Chessmaster:)
I have played chess mostly as a hobby and interest for several years now. I have gone to only a handful of tournaments. I have recently convinced my wife to take up chess as a hobby as well. It appears from the forum discussions that chessmentor, fritz and chessmaster seem to be the top contenders on software. Any suggestions about which one i should go with if im looking to primarily help my wife learn the basics in an easy to understand way, and hopefully gain some intermediate instruction for myself?