GIFs and 8-bit PNGs only support "simple" transparency, that is, each pixels is either fully transparent or fully opaque. For "complex" transparency/translucency/alpha channel, you need 24-bit PNG. There are other image file formats that support it, but PNG is what modern browsers support. You should be able to select "PNG (24-bit)" from most decent image editors, or otherwise if there's only one PNG option, you sometimes have to check a box reading "Alpha channel" or something else related.

You may want to note that some ancient browsers do not handle alpha channels. IE6, for example, displays a gray background for PNGs with alpha channels. There is a proprietary filter you can use to get around that, though, if IE6 is important. In that case I'd advice you to Google it and read up on it a bit.