The usual explanation of how network interfaces get their names is that they're named based on what's in /etc/modprobe.conf (/etc/modules.conf if you're still running a 2.4 series kernel). You'll have lines like:

alias eth0 sk98lin
alias eth1 3c59x
alias eth2 e100

And indeed this usually works, and when your system boots nicely the 3Com 'Marvell' gigabit card is eth0, the 3Com 'Cyclone' 100mbit card is eth1, and the Intel 100mbit card is eth2. Then one day you boot your system single-user without network interfaces enabled and decide to bring up just eth1, so you do 'ifup eth1' (or just 'modprobe eth1'). And the world explodes in your face, because the nice simple explanation is a white lie.

How the Linux kernel really names network interfaces is that network interfaces are named in the order they're found: the first network interface found is eth0, the second is eth1, and so on. The names in the 'alias' lines in /etc/modprobe.conf don't get passed to the kernel; they just help make the normal configuration more generic.

So when you do 'modprobe eth1' on a bare system modprobe maps 'load eth1' to 'load the 3c59x driver', the driver finds a card with a single network interface, and as the first found it becomes eth0. Kaboom. (Similar things can happen if you remove a network card.)

If you want stable names, the kernel does support renaming network interfaces; the usual approach is to name interfaces based on MAC addresses. On modern kernels you can use udev rules (see here); there's also nameif, and your distribution may already support it with the right magic settings.

(On Red Hat and Fedora Core, I believe that you set HWADDR in the ifcfg-* file in /etc/sysconfig/network-scripts. I'm not sure what Debian uses.)

The kernel uses registration order based naming for other things too; the most famous (or infamous) case is SCSI drives, where the first one found is sda, the second one sdb, etc. (The kernel treats SATA drives as SCSI devices, so more and more people may have to care about this one.)