Basically, "Ubuntu is based on Debian" means that several years ago, a group of developers took the source code and model of Debian and began to modify it, and evolve it, to the point that after a while it no longer looked or worked so much like Debian. It had become it's own animal, so to speak.
In the realm of genetics, this would be like going from one organism, to a mutant, to a new organism.
Linus Torvalds developed the Linux kernel and distributed its first version, 0.01, in 1991. It was distributed first as kernel sources only, then as a pair of downloadable floppy disk images, one bootable and containing the kernel, the other a set of GNU utilities and tools for setting up a file system. Since the installation procedure was complicated, especially in the face of growing amounts of available software, distributions sprang up to simplify this.
Early distributions included:
H. J. Lu's "Boot-root", the aforementioned disk image pair with the kernel and the absolute minimal tools to get started
MCC Interim Linux, which was made available to the public for download on the FTP server of University of Manchester in February 1992
TAMU, created by individuals at Texas A&M University about the same time
SLS (Softlanding Linux System)
Yggdrasil Linux/GNU/X, the first CD-DI-LDO based Linux distribution
SLS was not well maintained, so Patrick Volkerding released a distribution based on SLS, which he called Slackware, released in 1993. This is the oldest distribution still in active development.
(see http://en.wikipedia.org/wiki/Linux_distribution for more info)
In a nutshell though, it basically means that one distribution is derived in part or wholly from the source code of another distribution. With the majority of Linux Distributions being released under the LGPL3 license, anyone is free to use, modify, and distribute any software released under that license, including their own modifications. The only stipulation is that if you base a release on the source code of another, you must release your changes to the source to make them equally available for others to do the same.