I suppose that frequencies were randomly assigned letter names
here we have A4 = 440Hz
C3 here = 130.81Hz
C4 here = 261.63Hz
C5 here = 523.25Hz
How is C3, C4 and C5 related? How are they all "C"?
They are in different octaves. They sound the same to the human brain, because it's wired this way and I have no idea why. It's a phenomenon called the Octave Illusion. Also, every upper octave is twice the frequency of the lower, as @KirkA meant, citing the powers of two.
This illusion, combined with our tendency to "like" multiples of a base frequency, brought us to define all the tones in all the musical scales. They initally all related to the base, called "tonic", frequency by a factor, then things became more complicated... because of a number of reasons. A long number of reasons.
They are all different octaves. And octave are related by frequency in the powers of two. For instance, C5 is twice the frequency of C4 -- that is, C5 = C4 x 2. And C4 = C3 x 2, and so on.
To expand on Kirk's answer, in equal temperament (the most commonly used, to my understanding), each successive note is tuned 2^1/12 Hz above the previous. Since there are 12 named notes, this means that each repeated note is twice the frequency of the previous note of the same name.
Also, in a resonance column open at both ends or a string fixed at both ends, the octave is the first overtone of the fundamental frequency. This may go some way to explain why we hear octaves as "special".
'Pitch class' is the term for tones grouped by octave:
C2, C3, C4, etc. https://en.wikipedia.org/wiki/Pitch_class
'Octave equivalency` is the term for the perception that tones of the same pitch class - tone differing by an octave - are all the same. https://en.wikipedia.org/wiki/Octave#Octave_equivalency
All these answers are great but I think it's helpful to remember that between C3 and C4 you always have 11 notes. Same thing between C4 and C5. You can do that forever and it will always be 11 notes between the start of one octave and the beginning of the next.