This is finally answered in Season 6 Episode 7, "The Broken Man". The episode starts with a cold open in some religious camp. At the end of the scene one of the men is revealed to be Sandor Clegane. Ray and Sandor have a conversation later on about what happened to him.
Ray: When I found you, I thought you’d been dead for days. The way you were stinking already and you had bugs all over you and bone was coming through right there. I was gonna give you a proper burial and then you coughed. Oh, nearly shit myself. I reckoned you were gonna die by the time I loaded you on the wagon, but you didn’t. Now, I reckoned you’d die a dozen more times over the next few days, but you didn’t. What kept you going?
Game of Thrones, Season 6 Episode 7, "The Broken Man"
So in short he was found on the verge of death by Ray and then nursed back to health with a few death scares along the way. Since then he's been helping out Ray at his encampment.
You can view the scene here.