Etiquette for declining a tenure track job offer
I would say that the most appropriate medium would be to send a written communication, either as an email or as a letter. This carries much more weight than a phone call, as you actually have something resembling a paper trail that you can provide. 

Although there is a certain wisdom in the advice "contact them as they contacted you," this is an exceptional enough situation that deviating from that rule seems more appropriate.

The route that I would use is to write a formal, signed letter, then scan it in and send a copy of the scanned letter as a PDF to the intended recipient. The scan will reach them more quickly, and you'll still have the formal communication sent by regular mail.