I started using linux when I was 13/14 yo, can't remember exactly, and my HP notebook, with Windows XP, had a BSOD. I was tired of having to install drivers, and many programs by going in their website and downloading then, also, anti-virus was boring, and time to time I had to wipe the HD and start clean because the system was very slow.
So I remember I googled "free operating system", and that's how I heard about linux for the first time. So I started installing distros in my machine. The problem at the time was the internet connection, it was slow, and I had to connect using PPPOE because that was the internet service I had in my house. And this alone made many distros to not work for me, since I could not connect to the internet, I had to find another distro.
I tried debian, knoppix, fedora, mandriva, sabayon (had a beautifull interface), big linux, open suse, gentoo; but I used then only a little. I could only explore what they installed from the live CD, and if I could'nt find the pppoe setting I had to uninstall it and go to the next distro. I had very limited knowledge on how a linux system worked, and which programs came in the live CD, at that time the website I accessed the most was problably distro watch.
Things changed when I installed Mepis linux, it had an easy way to setup the internet. So I could connect using cable and browse the internet.
So I explored it, first thing I did was learn to install packages, if you're new to linux, one of the best things about it is package management, and Mepis was debian based. So I learned how to do a sudo apt-get install [pack] and installed compiz. But then I wanted my wifi chip to work, I was using cable and that's inconvenient, thus, I starred at another problem: wifi support and proprietary drivers.
So my piece of advice so far for choosing a linux distro is:
At that time wifi chips, like my Broadcom BCM4312, were new and drivers were hard to find, my option was to use the windows driver with ndiswrapper, and that was complicated for me. There was a website dedicated to gathering info on wireless cards support on linux, it has changed a little sinc: linux wireless. And that helped me a lot setting up my Broadcom card.
Another issue was my nvidia card, it was a GeForce 6200, really good card, but the only decent driver was the proprietary nvidia driver, which I had to head over to the website, download some weird file and execute it. It sometimes failed to install, and I had to use the distro without 3d acceleration support, at that time the nouveau driver was giving its first steps, so no 3d support, and poor 2d performance. I think it really evolved from that time but I'm not sure if it is good for gaming today. I remember accessing phoronix very oftenly, anxious for benchmarks on the newest driver, Michael Larabel deserves my kudos for all the incredible work he has been doing, and still does, for the linux, open-source and benchmarking comunities.
Fortunately Ubuntu came next and solved both problems for me, it had the network manager applet that worked like a charm, and the proprietary drivers menu was easy to configure and add the nvidia driver, but after installing I had some issues with the splash screen, no big deal. I could even play gnome games which came pre-installed and Counter Strike using Wine!
That distro also had some quirks, it was unstable, sometimes I broke my system by installing/updating packages, I was doing all sorts of things with it, and had to reinstall it using the CD I bought on a newspaper post. My real problem with ubuntu was upgrading it, it was easy to break by doing a version upgrade, it still is. I was enjoying using ubuntu, but sometimes it pissed me off with outdated software, I needed some new software, like wine, drivers, and ubuntu didn't have the newest versions. So take this into account when choosing your distro, debian packages are much more stable and updated less frequently, hence, debian and debian based distros often contain packages that are slightly outdated. If you need bleeding edge software without having to upgrade the whole system, like me, you may want to use a rolling release distro.
So I went to google again, and searched: rolling release distro, guess what I found...
Arch has a difficult installer, it is text based, and it makes you choose the software. I had to start over a couple of times because I missed some important packages. It uses the pacman package manager (great name), which I think is simply incredible. The good part is that I learned a lot about how a linux system works, how to configure it and what it needed to run. I really miss the BSD style init, now it uses systemd, sadly. The best part about it are the wiki pages, which are really great and complete, also arch has the AUR, archlinux user repository, which contains packages submitted by users. I always find the packages I need there.
The only bad thing is that it not user friendly, so most users do not use it, it comes with the bare minimum (I like it), and lets you choose what to install next. Almost all configuration must be done by hand, and that includes you learning it, so it becomes tedious to use. There are some archlinux based distros which may help on this, so you may want to check them out, I'll stick with arch, for now.
To sum it up, my two cents on what take into account when choosing a linux distro is, the previous points, plus:
And if nothing really pleases you, consider rolling your own distro, or building lfs. I already tried it and it was a great trip, this is, IMHO, the ultimate way to learn how a linux system works. And it does not end here, you can try something totally different too, like a BSD.