Весь ненужный фон заливается каким-нибудь одним сплошным цветом,

Весь ненужный фон заливается каким-нибудь одним сплошным цветом, желательно не совпадающим с остальными, иначе получается именно то, что вышло на первой картинке. А дальше остается только сохранить картинку как GIF с прозрачностью, выбрав этот цвет в качестве фонового.

PS А как сделать именно в Фотошопе - не знаю, я обычно IrfanView пользуюсь для конвертации, больно уж там это просто и наглядно.