I use Photoshop 7.0 and IconBuilder Pro (in the pre-32-bit days, I used Resedit to make final touches).
For Mac OS X 128x128's, I usually take the 32x32, resize it to 128x128, trace the parts on a new layer, shade the parts, and add details. It's really time-consuming, but worth it.
I don't work large and then shrink it down, at least for the 32x32's...for me, it gets too muddy that way. I do sometimes shrink down the 32x32's to make the 16x16's.
I usually have a normal sized view (to preview) and an enlarged view (to work in).
People ask about inspiration...ha! I just start doodling. Maybe one in five icons were purposefully made. Some of the icons are parts of other graphics I've done. For the Gort's Icon's series, there is no theme whatsoever...it's just a big grab-bag of oddness.
If I see something I recognize/like in the scribble, I start shading it.
Next comes the color. A lot of the time, I'll look for colors I haven't used in the collection yet.
Friends that watch me work (the ones that have Photoshop experience) can't believe how many Photoshop layers I end up with when I'm done with an icon.
For Windows conversions, I used to paste the icons into MicroAngelo (running under Virtual PC)...now I use IconBuilder Pro. For the .gif conversions, I use IconToGif.
I get email from people wanting to make icons, asking for tips...my answer is this: MORE RAM. If your icons don't look cool, it's because you don't have enough RAM. Continue installing RAM until your icons look great.