How can a Linux OS be "based on" another Linux OS?

Linux is a kernel, Debian is a distribution of that kernel and a bunch of software to actually interact with the system.

I can now take Debian and change the logo on the boot screen to my own logo and then my distribution is based on Debian (in a very primitive way). Usually, the adjustments that are made in a derived distribution are more substantial.

The point is, if you would want to change something about a distribution, then you can just take that one, modify it to your liking and then publish your own distribution, based on the existing one (as long as all licences are respected).

Linux is a kernel — a (complex) piece of software which works with the hardware and exports a certain Application Programming Interface (API), and binary conventions on how to precisely use it (Application Binary Interface, ABI) available to the "user-space" applications.

Debian, RedHat and others are operating systems — complete software environments which consist of the kernel and a set of user-space programs which make the computer useful as they perform sensible tasks (sending/receiving mail, allowing you to browse the Internet, driving a robot etc).

Now each such OS, while providing mostly the same software (there are not so many free mail server programs or Internet browsers or desktop environments, for example) differ in approaches to do this and also in their stated goals and release cycles.

Quite typically these OSes are called "distributions". This is, IMO, a somewhat wrong term stemming from the fact you're technically able to build all the required software by hand and install it on a target machine, so these OSes distribute the packaged software so you either don't need to build it (Debian, RedHat) or they facilitate such building (Gentoo). They also usually provide an installer which helps to install the OS onto a target machine.

Making and supporting an OS is a very complicated task requiring a complex and intricate infrastructure (upload queues, build servers, a bug tracker, and archive servers, mailing list software etc etc etc) and staff. This obviously raises a high barrier for creating a new, from-scratch OS. For instance, Debian provides ca. 37k packages for some five hardware architectures — go figure how much work is put into supporting this stuff.

Still, if someone thinks they need to create a new OS for whatever reason, it may be a good idea to use an existing foundation to build on. And this is exactly where OSes based on other OSes come into existence. For instance, Ubuntu builds upon Debian by just importing most packages from it and repackaging only a small subset of them, plus packaging their own, providing their own artwork, default settings, documentation etc.

Note that there are variations to this "based on" thing. For instance, Debian fosters the creation of "pure blends" of itself: distributions which use Debian rather directly, and just add a bunch of packages and other stuff only useful for rather small groups of users such as those working in education or medicine or music industry etc.

Another twist is that not all these OSes are based on Linux. For instance, Debian also provide FreeBSD and Hurd kernels. They have quite tiny user groups but anyway.