How do I design a device to automatically switch to the backup battery?
Why don't all devices use this?  It adds cost and complexity.  Is their any other reason for not doing something?

Seriously, I'd say that there are plenty of options and implementations for this.  Having two equal batteries doesn't make much sense, so often the second is used for emergency or limp-home power.  For instance, your PC has a RAM retaining battery on the motherboard for when you loose power.  A laptop often gives a "Low battery" warning, at which time you're welcome to reduce power however you can.

I think that your statement that 'batteries work best if they are used until they are completely drained, and then recharged.' is a little broad.  This is more the case for Nickel-based (NiCd and, to a lesser extent, NiMH) chemistries.  Lithium Ion cells don't suffer this memory problem.  In fact, their lifetime improves if you avoid deep discharges.  See this page from BatteryUniversity.com for reference.

There are a couple of options for doing more intelligent power management in your own devices.  

The simplest is an ORing diode on the power supply.  If all you want is a hot-swappable power supply and you have a bit of leeway for your inputs, you can connect backup battery to the anode of a diode, and connect the cathode to your main battery.  When the voltage of the main battery dips to 0.7V less than your backup (Or is removed), the other battery kicks in.  Be careful of leakage current into the backup battery, it might overcharge it.

Alternatively, you can use a power mux IC like the TPS110.  This lets you select your input independently (or dependently, if you prefer) of the input voltages, instead of always using the higher supply.

Finally, Linear Technology incorporates what they call "PowerPath" controllers into their battery charging ICs.  I've used their LTC4011 which seamlessly transitions between battery and external power, and charges the battery while running off of the external power.