The article that influenced me to write this was “How to Build a Low-tech Website?” by LOW←TECH MAGAZINE.
GIMP
Image → Mode → Indexed. Check the box “Remove unused and duplicate colors from colormap”. For dithering I recommend you choose “Floyd-Steinberg”. Whether you want to use colors or not is up to you. After you are satisfied with the result, export as a PNG and try removing as much metadata from the image as you can to help aid in lowering the size even more.
ImageMagick
# Using ordered dithering (less detail but smaller filesize)
convert input.png -scale 600x -colorspace gray -ordered-dither o8x8 output.png
# Using Floyd-Steinberg
convert input.png -scale 600x -dither FloydSteinberg -remap pattern:gray50 output.png
# The `-scale` flag is there to resize the image to a width of 600. You can
# change the width to something bigger, or smaller (won't recommend), if you wish.
Dither it!
An online image dithering tool that’s easy to use. Not much else to say, try it out!