It is narrated from Tawus (may Allah have mercy on him): Cleaning oneself with three stones or three pieces of wood is (the Sunnah). I said: And if they are not found? He said: Three handfuls of earth. This is what is authentically established from Tawus (may Allah have mercy on him).
Hadith Referenceالسنن الكبرى للبيهقي / كتاب الطهارة / 537
Salamah bin Wahram said: I heard Tawus (may Allah have mercy on him) say that the Messenger of Allah (peace and blessings be upon him) said: "When one of you comes to relieve himself, let him honour the qiblah of Allah: let him neither face it nor turn his back to it. Then let him clean himself with three stones, or three pieces of wood, or three handfuls of earth. Then let him say: 'Al-hamdu lillahil-ladhi akhraja 'anni ma yu'dhini wa amsaka 'alayya ma yanfa'uni' (All praise is for Allah, who removed from me what harms me and retained for me what benefits me)."
Ahmad bin al-Hasan al-Mudari, who narrated it from Abu Asim from Zam'ah, is a liar and matruk (abandoned). Neither its connection (through Ibn Abbas) nor its attribution to the Prophet (peace and blessings be upon him) is authentic.
Hadith Referenceالسنن الكبرى للبيهقي / كتاب الطهارة / 538
It is narrated from Sayyidah Aishah (may Allah be pleased with her) that Suraqah bin Malik came to the Prophet (peace and blessings be upon him) and asked about relieving himself, and he ordered him "to keep himself upwind, to neither face the qiblah nor turn his back to it, and to clean himself with three stones in which there is no dung, or with three pieces of wood, or with three handfuls of earth."
(b) Imam Abu al-Hasan al-Daraqutni (may Allah have mercy on him) said that no one narrates this except Mubashshir bin Ubayd, and he is matruk al-hadith (abandoned in hadith). The Shaykh said: It is reported from Sayyiduna Anas bin Malik (may Allah be pleased with him) as a marfu' narration, and that is rejected.
Hadith Referenceالسنن الكبرى للبيهقي / كتاب الطهارة / 539
It is narrated from Yasar bin Numayr, the freed slave of Umar, that when Sayyiduna Umar (may Allah be pleased with him) urinated he would say: Give me something with which to clean myself. The narrator said: I would hand him a piece of wood or a stone, or he would come to a wall and wipe himself against it, or touch the ground, and he would not wash it.
This is the most authentic and the highest of what has been narrated in this chapter.
Hadith Referenceالسنن الكبرى للبيهقي / كتاب الطهارة / 540