Musannaf Ibn Abi Shayba 16:688

Abu Bakr narrated to us, he said: Waki' narrated to us, from Shu'bah, from Muhammad ibn Ziyad, from Abu Hurayrah, who said: The Messenger of Allah (may Allah bless him and grant him peace) said: "When one of you puts on his sandals, let him begin with the right, and when he takes them off, let him begin with the left."