1. Make sure you have your image on its own layer with no background.
This is the #1 mistake people make, in older versions of Photoshop you would have saved it on a colored background
2. Now go File>Save for web
You should see this box open.
3.Make your setting gif and use the smallest amount of colors you can without affecting the appearance of the image.
The 2 things to remember here are:
- Make sure Transparency is selected.
- Set the Matte color to the closest match of the background color you will be placing the image on. If you are unsure then set the Matte to "None" (more about Matte in step 4)
Click ok and save your image.
4.
Some more information on Matte.
Matte puts a thin outline around the image to get rid of what we call halos.
On the right you can see an example of a halo. Look familiar? This is the sign of an amateurish webpage. Believe me there are already enough bad webpages out there without us adding to them. :)

5. Here is the same image with Matte set to none. Notice the halo is gone, but it is still a bit jaggy around the edges.

6.
Here is the same image, this time saved with a black Matte. Notice how nice and sharp it is?

Always choose a matt color if you can. This way all your transparent gif's will look nice and clean.
This Matt trick will also work with transparent PNG's.
Stay tuned for more :)
About the Author:
Colin Smith is a best-selling author, trainer, and award-winning new-media designer
who has caused a stir in the design community with his stunning
photorealistic illustrations composed entirely in Photoshop. He is
founder of the world's most popular Photoshop resource site, PhotoshopCAFE.com, which boasts more than two million visitors.
With over 10 years of experience in the design industry, Colin was formerly Senior Editor and Art Director for VOICE magazine. He is a regular columnist for Photoshop User magazine, PlanetPhotoshop.com, and the official site of the National Association for Photoshop Professionals. He also contributes to a number of other graphic art publications and Web sites, such as Mac Design magazine, Web Designer magazine and Computer Arts Magazine.
Colin's graphic design work has been recognized with numerous awards,
including the Guru awards at Photoshop World 2001 and 2002, for his
work in both Illustration and Web Design. He's authored or co-authored
more than ten books on Photoshop, including the best-selling How to Do Everything with Photoshop CS (McGraw-Hill/Osborne, 2003) and award-winning Photoshop Most Wanted: Effects and Design Tips (A Press/Friends Of Ed, 2002). Colin is also creator of the Photoshop Secrets Video training series (PhotoshopCD.com).
He is in high demand across the United States as a lecturer, presenting
his Photoshop techniques to Web designers and other graphics
professionals across the nation.