Any kind of air compressor works great, especially on long-neglected machines. I have a small compressor at home, but if I didn't, I wouldn't hesitate to take some of the 'puters I've seen to a friendly gas station. Yuck. Keep one hand on the case, the other on the nozzle, blast away. A canister vac and canned air work OK, too, just not as effective.
Old toothbrushes work well on the really crusty bits, or any kind of brush that will reach into the crevices. I've heard of people washing the boards with dish detergent & water, which I thought was nuts, until we got a miniature steam cleaner at the shop where I work that's made just for cleaning computer boards. Haven't tried it on my own stuff, but it blasts the crap right off of the company's industrial computer components.