An important source of information is comparison to other languages.
For example, Cicero was spelled as Κικέρων1 in Greek.
If we believe that the Greek kappa was pronounced as /k/ rather than /s/ or /ts/ or anything else, we can be confident that c was pronounced as /k/ in Latin as well — at least in this name.
Similarly, the name Caesar gave rise to the present German word Kaiser.
The loan was, as far as I know, made in the ancient times.
If we know something about how the pronunciation of German(ic languages) evolved, we know something more about how Caesar pronounced his name.
1
Thanks to chirlu (see comments) for the correct Greek accent and the final nu.
I don't know if the final nu was used in all occasions, but that is besides the point.
:-)