Free Software: GIMP / Aviary.com
Commercial: PhotoShop and Fireworks
If you've got the money, go for Photoshop. You can find tutorials literally anywhere, just google "web design tutorials" and you'll find them of all levels, basic to advanced.
Just keep practicing, trying new techniques and applying various styles to the design you make.