This is done by adding a <deleted-entry>
Atom entry to the transaction Bundle, much like it's done when returning a Resource's history (which can contain deletions as well).
You can find information about it here: http://www.hl7.org/implement/standards/fhir/xml.html#atom-deleted. It's actually a pretty recent addition to the Atom specification (see http://www.rfc-base.org/rfc-6721.html for more information).
The Java reference implementation has a setDeleted() on AtomEntry to make that work.