I would say perhaps some quick sketches on paper and then careful pixel placement by hand in DPaint. He obviously had a great skill at making the most of the palettes and doing dithering manually. You just have to do stuff like this a lot to get the "feel" for it - there are no absolute rules and set techniques. His C64 art experience most likely helped a lot on the way.
