It doesn't really fit with the image of Julius Caesar to be referred to as "hairy", or did the Roman cognomens have a different function than what we would commonly refer to as a nickname?
Gaius Julius was not the first of his family to be called Caesar. It was a family name, so any possible meaning of the name must be applied to some unknown ancestor, not to the famous historical figure. That said, while the true origin is irretrievably buried in the sands of time, there are several possibilities that have been proposed since antiquity:
"Hairy," as you said, though it may have been an ironic name referring to baldness, which Caesar quite notably was, and possibly his ancestors too. Self-deprecating names were not uncommon. Cicero means chickpea, which Plutarch says refers to an ancestor's warty nose.
Ancestor born of Cesarean section, from caedere "to cut." This was a risky operation where the death of the child was possible and that of the mother almost certain. Surviving and making it to adulthood would be pretty special.
Ancestor killed an elephant in battle, from caesai, supposedly a Punic word for the animal. This was the interpretation that Caesar himself endorsed.
Blue eyes, from Caesiis oculis. Having blue eyes in ancient Rome would certainly be notable enough to earn you a cognomen in certain circumstances. Caesar's own eyes were likely brown (his contemporaries call them black, which probably just means very dark).
Some cognomen were hereditary (including Caesar), so it doesn't necessarily have any specific connection to his physical attributes.
But an ancestor of his may have been particularly hairy to get the name initially. (Or bald as a coot, some cognomina were used sarcastically, "Little John"-style).