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