Almost all of the time, they do it via just adding new features and not breaking old ones.
But yeah, GNU/Linux and Solaris both have symbol versioning as part of ELF (I'm not sure if other executable formats have it; it doesn't actually require very much out of the format). The approach, roughly, is that each symbol in the file is named something like "memcpy@GLIBC_2.2.5", and if you see symbol versions in the library you're linking against, you include those references. The dynamic linker is also smart enough to resolve unqualified symbols against some default version the library specifies. This is important for backwards-compatibility, for the ability for distros to add symbol versions when upstream doesn't have them yet, and for things like dlsym("memcpy") keeping working. When they make a backwards-incompatible change (e.g., old memcpy supports overlapping ranges, new memcpy does not promise to do the right thing and you need to use memmove instead), they add a new version (e.g., "memcpy@GLIBC_2.14"). Anything compiled against the newer library will reference the new version, but an implementation of the old version still sticks around for older functions.
And yes, there were older versions before libc.so.6 - libc.so.5 was used, I think, in the early 2000s, but they've avoided changes since then. (The approach used there is that you can install both of them on a single system, but "libc.so" symlinks to one of them, and that name is used when you compile code. When you run gcc -lfoo, it looks libfoo.so, but if the library has a header saying its "real" name, called its "SONAME", is libfoo.so.1, the compiled program looks for libfoo.so.1 and not libfoo.so.) Now you only have to have a single glibc version and it works with many years of updates.
