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.
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.