We frequently get questions asking which distribution to choose. The short answer is - pick whatever distribution you're currently using if it's one that you like and are comfortable using. :) It's not going to make a tremendous difference at the end of the day and the differences are mostly in the way you'll manage your server and where/how config files are kept.
Our current recommendation, if you don't have a preference, is to go with Debian 5.0 (aka Lenny). Debian enjoys a vast software repository and you're likely to find anything you're wanting to run in the official repositories. This not only makes software installation easy, but it makes applying future security patches a breeze as well. Debian, and it's derivatives, are easy to upgrade in-place meaning that you can usually update your system to the next release without having to reinstall the server from scratch (Redhat, I'm looking at you). The release cycle was recently changed and I think it's now standardized on an 18 month schedule if I recall correctly.
Ubuntu has enjoyed popularity for the last couple years on the desktop and this exposure means that a lot of people are familiar with it already. It's a derivative of Debian and is managed in much the same way. They have 2 different release schedules (LTS and the normal distribution). LTS stands for long term support and is released every 2 years. The support window for this release is 5 years for their server release. The normal release cycle is 6 months with support expiring 18 months after release. This distro enjoys the same benefit of in-place upgrades as Debian.
CentOS is the free binary build of RedHat Enterprise Linux. It's essentially 100% binary compatible with RedHat packages so if you're not able to find a package for the software you're looking to install, chances are that you can grab a RHEL package and install that. You _could_ run into an issue, but I've not seen that happen before so it should be fine. The release cycle here is pretty long and it is an enterprise level distro. The packages are well tested and known to work reliably together at the expense of some of the latest package releases. You won't get cutting edge features, but you will get stability in spades. Also, some people find it easier to manage than Debian. Your mileage may vary. :)
Fedora - 6 month release cycle. 18 month support window. Can't be upgraded in-place. Do I need to go any further? Unless you like to reinstall your server every 18 months or just want the latest packages - everything else be damned, don't go here.
If you want to find out more about a particular distro or need to see which package versions are included, distrowatch.org is a great place to check that out.