There are lots of options when it comes to software, but only a couple when it comes to tablets. Wacom is the only manufacturer I trust, and they have two models that are within reach of most hobbyists. The Bamboo Fun is the cheaper of the two, and it's suitable for most users. The Intuos line is designed for professional artists, and it is twice as sensitive, plus it can detect the angle between the pen and the surface. It's a bit pricier, but sometimes you can find an older one, an Intuos2 or Intuos3, on Craigslist or eBay.
As for software, take a look around the Finished Maps forum and see what you like. Most of the time, the cartographer will either mention what software and techniques were used, or they'll have a list of programs they favor on their profile. A lot of people like the Gimp, a free open source program that has functionality similar to Photoshop. It is also common to pair Gimp with Inkscape, an open source vector program intended to compete with Illustrator. Inkscape isn't as mature as Gimp yet, but it's still quite a useful program.
There are also some programs dedicated specifically to mapping, such as Campaign Cartographer and Fractal Mapper.