Hmm... Tried the png... it seems like the transparency works in some places but not in others. For instance, it worked when I viewed it with windows viewer and when I viewed the image individually in photobucket. But on the main page of photobucket, it had a black background, and you can see the results here.
It gave me a lot of options when I went to save it, maybe I didn't select the right ones.
Oh and I did look for a dithering option to save it as a gif, but there wasn't any... but I'll check out the dithering options for when it gets converted from RGB to indexed.
Edit: This is what I came out with after playing with the dithering options:
I'll probably just abandon the airbrushing thing if you guys don't have much more in the way of suggestions.
Thanks for helping me with this.
I'm finally back for the summer, although hopefully I'll spend a little more time away from this screen.