Sayyiduna Abdullah bin Abbas (may Allah be pleased with them both) narrates: The Prophet (peace and blessings be upon him) ordered us to apply henna, and forbade (dyeing with) black.
Al-Bazzar recorded it. Its chain contains a narrator, Yusuf bin Khalid al-Samti, who is da'if (weak).
Hadith Referenceمجمع الزوائد ومنبع الفوائد / كتاب اللباس / 8783