It appears to be primarily by someone else ritually bloodying up the murderer's hands.
The only place I have found a scene actually describing the ritual of purification from murder in Greek mythology is Book 4, Lines 685-718 of Apollonius Rhodius' Argonautica, in which Medea and Jason are welcomed by Circe upon her island of Aeaea.
She seems to know intuitively that they are guilty of murder, though she does not appear to be bothered about whose murder it is until after the ceremony she causes them to participate in. Afterwards, when she finds out all the details, again seemingly through intuition or some other supernatural means, she immediately ousts them from her home.
The ritual is quite elaborate and at least one part of it surely is unique to the way Circe would have done it, as opposed to, say, Proetus or Eurystheus. Circe's attendants were Naiads (water-nymphs) and they participated in the ceremony, though perhaps they were not crucial to its efficacy or legitimation: they carried out of the house the defiling refuse which had remained from the ritual. Proetus and Eurystheus probably did not have access to Naiads.
In these murder stories it seems almost customary for the murderer to be banished from his homeland or to flee, becoming a suppliant in a foreign city or land. According to Apollonius, suppliants possessed rights protected by Zeus Hicesius, the "Cleanser," who seems to have expected these suppliants to be granted the hospitality of a purification sacrifice in the place in which they felt safe enough to request such succour.
In obedience to this ordinance, on behalf of Jason and Medea, Circe
began to offer the sacrifice with which ruthless suppliants are
cleansed from guilt when they approach the altar. First, to atone for
the murder still unexpiated, she held above their heads the young of a
sow whose dugs yet swelled from the fruit of the womb,
apparently a newborn piglet, whose throat she slit. Jason's and Medea's hands were then drenched in or sprinkled with the blood dripping directly from the piglet's neck. It was upon their hands presumably because those were the instruments which had been used to commit the crime.
Then with further propitiating libations [drink offerings], she
called upon Zeus Hicesius, the protector of blood-guilty suppliants.
And all the polluted scourings were gathered and carried out of the
palace by the attendant Naiads who did her housework.
But she herself stayed inside by the hearth, burning wineless
offerings and cakes of flour, oil and honey, and offering up prayers
that the terrible Erinyes [Furies] would cease from their wrath, that
Zeus himself would look kindly on them, and show gentleness to them both,
whether the hands they lifted up to him were stained with a kinsman's
or a stranger's blood. Only when all was accomplished did she make
them get up.
Medea and Jason were then seated on polished chairs, but after a brief conversation in which Circe discovered the full extent of the couple's misadventures, Circe summarily shooed them out of her home.
The labours performed by Heracles were special contrivances which different deities with conflicting motives orchestrated for him to accomplish. The main divinities in question here are Hera and Zeus. Hera wanted any means she could employ to get Heracles killed. According to Diodorus Siculus' Library of History 4.9.5, Zeus, on the other hand, way back when Heracles was still a baby and before he had even committed any ill, had made a deal with Hera that, after Eurystheus and Heracles had grown up,
Heracles should serve Eurystheus and perform twelve labours, these to
be whatever Eursytheus should prescribe, and that after he had done so
he should receive the gift of immortality.
On his own end, meanwhile—even though in a sense these aspects of his life had been planned out for him beforehand—Heracles himself found out, via instructions from Apollo, that he would become immortal if he enslaved himself to Eurystheus for a certain period of time and performed the tasks to which this king would assign him.
Therefore, while there is certainly a strong connection between the labours and his family's murder, it does not appear that Heracles was especially obligated to engage in these actions, or that he did these deeds under much duress, if any. And yes, he ended up doing these things because Hera hated him, but there was no official directive from anyone which said that the scorn of the goddess particularly required anything of him for his purification.
According to Apollodorus (Library 2.4.12), by the time that Heracles was receiving the stipulations for his acquisition of immortality, he had exiled himself from Thebes and already been purified by King Thespius of Thespiae. The most direct link made here to Hera's sentiments about him is that the Oracle of Delphi renamed him.
The Pythian priestess then first called him Heracles, for hitherto he
was called Alcides,
meaning "Offspring of Alcaeus," Alcaeus having been Alcides' grandfather. Renaming him Heracles, meaning "Hera's Glory," was apparently supposed to appease Hera. It does not seem to have worked.
