You are right about using GIF or PNG, but you need to delete the background layer so that you can see the transparent chequer board around your logo before saving. PNG is probably your best choice.
By the way, you probably want to save in the sRGB color space, and you should keep in mind that File - Save As - PNG embeds a color profile in your PNG while Save For Web does not.
You want a PNG-24, which gives you 16 million colors as well as 256 levels of transparency.
Not exactly a logo, but have a glance at this to see what's possible: http://Noel.ProDigitalSoftware.com/temp/TransparencyTest/TransparencyTest2.html
Noel is the leopard inside the sphere? I initially thought it on the outside and wondered why it was not sphereised before deciding it must be a glass ball, and that if you gave it a shake, it would be snowing inside the ball.
That's strange.... this time around it worked just fine without flattening or any special settings (I just enabled "transparency" and left Matte to "None" by default) when doing "Save to web"! What's "Matte" for anyway? The tooltip says that it's used for blending the transparent pixels against the background, but maybe that's more for semi-transparent pixels?
Perhaps it working had something to do with me installing the latest Photoshop upgrade patch a few moments ago prior to trying it again. In any case I got it working.
Noel: I didn't know that it didn't save the sRGB profile in "Save for web" -so what's the difference between "Convert to sRGB" and embedding the sRGB profile in the image? I guess I really didn't need to check "Convert to sRGB" as I created the image with the sRGB profile to begin with.
Oh, and converting the image from 300 DPI down to 72 DPI is also a very good idea
Trevor, that's a photo of a spherical puzzle.
If you create the image in the sRGB profile, you're right - you need do no conversion, mixapix.
The pixels/inch value doesn't matter for web images. But you'll notice that the image in my web page above is actually downsized so that it doesn't break down if you zoom your browser (more likely on something like an iPad). Just food for thought.