I used to build/program embedded systems (around a 6800 uP). I'd debug using an oscilloscope, sometimes an LED attached to a pin, sometimes connecting the pin to a speaker (!). There wasn't enough EPROM space for a printf. And besides, the turnaround time for erasing/blowing an EPROM was just too long.

Essentially you just get good at staring at the code and running gedanken experiments till you figure it out.