How do the tiny AC->USB power supplies work?

This is not limited to these USB charger supplies. Most modern "wall wart" type power supplies are like this. They can be small because they are switchers. The line power is full wave rectified, then the result chopped at high frequency thru a transformer. The much higher frequency allows for a much smaller transformer to handle the same power. 5 Watts (5 V at 1 A) is easily doable in something that fits in the palm of your hand.

If you dig around, you can probably find a schematic for a small switcher like this. It is usually a full wave bridge, cap, and some sort of oscillator driving the primary of a small transformer at a few 100 kHz. The output of the transformer is rectified, filtered, and the result compared to the voltage setpoint. The over/under voltage indication is then transmitted back to the oscillator on the high voltage side via a opto-coupler.

The Apple iPhone charger is a switching power supply, complete with tiny flyback transformer. It works pretty much as Olin Lathrop described. It uses a L6565 controller chip that drives the switching MOSFET at (I believe) 70kHz. The Apple charger is more complex than the typical charger, using a quasi-resonant flyback topology. (The $2 chargers usually just use a ringing choke converter, and name-brand chargers use flyback topology.) I've posted a detailed teardown, explanation, and schematic of the Apple charger at http://www.arcfn.com/2012/05/apple-iphone-charger-teardown-quality.html