This originally appeared on the Annexe.

Using ImageMagick:

convert -type grayscale -depth 8

Using GraphicsMagick:

gm convert -type grayscale -depth 8