I don't think there's anything particularly remarkable about that. Rodrigo was a soldier of fortune, a profesional warrior since he was a child, and as such, a quite competent one. Battle-hardened in the Castile civil wars, he spent the rest of his life as a mercenary fighting for whoever who hired him.
He's far from being the only one mercenary who has kept by his side a fanatically loyal army of followers. Apparently he was a good commander, won most of the battles he fought and managed to cover his loses when not. That's enough to keep morale high. Soldiers do appreciate serving under capable commanders who either win or retreat without much carnage.
I don't think we can answer in a more authoritative way than this, though, since most of what we know about the person himself is a complete fantasy novel known as "El Cantar del mío Cid". The true(ish) facts about his life and deeds are known, but offer no insight about his personal charisma, or even his tactics and capabilities as a commander. The most trustworthy account on his life is the Historia Roderici, which is very scarce on descriptions on Rodrigo as a person, but at least seems to get the facts right - and acknowledges its own unaccuracy, which is always a sign of integrity.
For example, the main text about the Cid, the Cantar del mio Cid presents Rodrigo as a member of the aristocracy (there are no traces of his family name among the known records of Castillian nobility), who had two daughters, Sol and Elvira (they were indeed two, but their names were Maria and Cristina) and fights defending the Christian faith (no mention of his lenghty time at the service of Muslim rulers) alongside his closest advisor, Álvar Fáñez (who actually didn't follow Rodrigo to exile, staying in Castile all his life). Modern historians tend to concede between "zero" and "nil" credibility to the poem, whose only merit consists in being one of the earliest compositions in castillian language.