If you don't want to do vector, GIMP is awesome and free; it's what I use to do decals and all my graphics work in anyway. There's a lot of good tutorials on the internet, and many PS tuts can be adapted easily to GIMP. GIMP has a lot of plug-ins and filters as well as brushes and patterns available, and if you find PS brushes you like you can use them in GIMP as well. GIMP also opens .psd, PS' default filetype, so you can download and edit them.
Inkscape is a good free vector program, I've never used it though.
I find that GIMP works magnificently as well. I haven't tried Inkscape yet either, I'll look into that.