I'm one of the Photoshop junkies James mentions.

And I do think it's great, though I'm not really in a position to say it's better than other packages as I haven't used them extensively (or at all in some cases). One big advantage of Photoshop is that everyone else uses it too, so you'll find far more tutorials, brushes, filters, etc. out there for it than for other programs. One big disadvantage, of course, is that it ain't cheap. Also don't overlook Illustrator or other vector packages - most web people use Photoshop, but working with vectors has big advantages in some cases.
James is right to say it will take a long time to learn. Photoshop doesn't do things the Microsoft way, which works when you know the program but can be frustrating and confusing at first. In my experience, though, learning to use the tool doesn't take nearly as long as learning to make pictures. Of course if you're already an artist and understand composition, colour and stuff like that, you'll have a big advantage. I'm certainly no expert, though (now I can get Photoshop to do what I want most of the time) I guess I'm no longer a beginner either.
One thing I should say is don't be scared of using other people's pictures. Here's an image I finished recently.
Most of it is my work (it certainly took me long enough

), but I still used 4-5 stock images of clouds and smoke in the background to add texture and interest. In other pictures I've relied considerably more on stock to get the outcome I want. Doing it all yourself is like
making a sandwich from scratch: sure it's possible, and quite probably delicious too, but buying bread and bacon from a supermarket is usually the pragmatic choice.
There's a lot of stuff out there on arty blogs and stock image sites that you're allowed to use in your own work, often with few restrictions.
Stock.xchng is one I use quite often. If you're prepared to pay,
iStock is another great resource. Also check out the stock on
DeviantART, though some of this is more restrictively licensed.
A few tutorial sites you should probably check out are
PSDTUTS,
Veerle's blog,
VECTORTUTS (Illustrator) and
Abduzeedo.
For inspiration / ideas, you may want to try
Vanderlay Design Blog,
Smashing Magazine,
FFFFOUND!,
DeviantART and
Best Web Gallery. There are loads more good sites out there too of course, such as
BittBox for free textures and brushes[/url] and
FontShop FontFeed for cool typographical news.