Do you have a sample of your logo? Usually I do what luggnut posted, go to Layer > Matting > Defringe. You can adjust the number of pixels it removes.
If it's a raster image like a photo, I have the best results saving as a .jpg or .png. If I create a simple button etc, saving as a .gif works best. .gif's can be finicky with effects like gradients, drop shadows, complex graphics etc. If you're putting your logo over a solid color area, sometimes you can change the background to the same color if you want to save it as a .jpg.
I wanted to do these cards as .gif's, so they would have the transparent background and I could layer them over the background:
http://www.odcustomtattoo.com/otool-tattoo-artists.html I wasn't happy with the result, so I "cheated" and saved them as .jpg's with the template as the background.