What is a Linux Distribution?
"A Linux distribution or GNU/Linux distribution (or a distro) is a Unix-like operating system comprising software components such as the Linux kernel, the GNU toolchain, and assorted free and open source software. Some proprietary software is found in certain distributions and is not free software. A Linux Distribution or distro, is created by individuals, groups and organizations from around the world.

Companies such as Red Hat, SUSE and Mandriva, and community projects such as Debian and Gentoo Linux, assemble and test the software before releasing their distribution. There are currently over two hundred Linux distribution projects in active development, revising and improving their respective distributions."

Here are some ways the various distros differ:

1) Whether the distro is free or commercial and uses "Free Software".
2) Number of packages available without looking for other sources of software. Debian is the biggy here with over 15000 apps.
3) The way updates are handled.
4) How security policies are handled.
5) How easy it is to install and use. How are programs installed and updated.
6) Package management systems:

The following are some examples of package management systems implemented by Unix-like operating systems:
* RPM, the RPM Package Manager. Invented by Red Hat, but now used by several other Linux distributions. RPM is the Linux Standard Base packaging format.
There are many higher level tools that use the RPM packaging format, simplifying the process of finding, downloading and installing packages and their dependencies, including
o YUM, used on Fedora Core.
o up2date, used on Red Hat Enterprise Linux. Although designed to talk to Red Hat Network, up2date can also source packages from yum and apt for RPM repositories, as well as local and directories.
o YaST , as used on SuSE Linux distributions.
o urpmi as used by Mandrakelinux/Mandriva
o APT for RPM.
* dpkg, used originally by Debian GNU/Linux and now by other systems. The .deb format used by dpkg was the first to have a widely known dependency resolution tool, called APT.
* Portage/emerge, used by Gentoo Linux and inspired by the BSD ports system.

7) Is it going to be around or is it a new distro.
8) "Comparison of Linux distributions"
9) The file system used. "Comparison of file systems"
10) The Window manager used. Window Managers for X
11) Desktop environment used or choices.
12) Does it have the features and hardware support that "you" need.
13) The documentation and support available.

A good place to start looking is "A Beginner's Guide to Choosing a (Linux) Distribution" available at Distrowatch.com

Most of the information provided here comes from the Linux Wikipedia

Linux is a registered trademark of Linus Torvalds.