I'm using Photoshop CS5 and I just took the magic wand and selected the parts of the background and deleted them, and then saved the file for web as a .gif.
Hope that explanation helps.
Yes, the edges are quite terrible, but I'm not good with that detail, yet.
If it's non-animated save it as a .png and that should save your problem. Another thing would be is when you go to create a new document in Photoshop, I think it's the last option, choose transparent as the option instead of color. Hope I helped .