If you are using an older version of Photoshop (ie 4 or less) you may also need to make sure that you do not have a 1st layer with color in it. Basically, add a new transparent layer, send it to the bottom of the stack, then export it as a gif89a and follow as above. It seems that Photoshop used to accept an image with the 1st layer with no alpha to be not available for alpha in gif export