Credit goes to Brontosaurus and rootbeer277 for pointing out some innaccuracies in the original version of my writeup. Thanks.
The ISO paper size system is based on the metric system and is used pretty much everywhere in the world aside from the United States, which is sticking to its own system.

In the ISO system, the ratio of the length of the paper to the width is 1.4142, or the square root of 2. This means that you can put two pieces of paper side by side and instantly have a piece of paper twice as big with exactly the same proportions.

If you have a hard time grokking this as I did, imagine two pieces of paper, each piece one unit wide and square root of two units long. When you put them together, the square root of 2 side would become the width, and the two ones added together would become the length of the new piece of paper. The dimensions would be square root of 2 units by 2 units, and the ratio would again be 1 to the square root of 2. Ingenious.

ISO Papers come in three size categories: A, B, and C. Because the square root of two is involved, the dimensions for ISO Paper aren't nice round numbers (like the US letter 8.5" x 11").

Because it is metric, the size system is ultimately based on the meter: specifically, the A0 size has an area of one square meter.

As the number gets larger, the size gets smaller, so an A1 is half the size of the A0, the A2 is half the size of the A1 and so on. A4 is the closest size corresponding to the US letter size.

The B size is the geometric mean between the An and An-1 sizes, so a B1 is sized between an A0 and an A1. The B0 is between an 2A0 (see below) and an A0, so it's the square root of 2 times as big as an A0. It's used when one size is a little too big but the next size is too small. Not widely used outside of drawing or graphic work.

The C size is the fourth root of 2 times the size of the corresponding A and is generally used for envelopes. A corresponding A paper size can fit unfolded in a C sized envelope.

Of course, anyone looking at this size system would see a problem: you're on zero here, all the way down, all the way down. Where can you go from there? Where? Nowhere.

So, to describe larger paper sizes, they've has added a few other players: The awkwardly named 2A0 is twice the size of the A0, and the 4A0 is, respectively, twice the size of the 2A0.

In addition, for printers there are slightly larger sizes (RA0, RA1, etc) that add margins for binding or trimming. And there are even more slightly larger sizes (SRA0,SRA1, etc) used for bleeds.