Minecraft wiki entry for Anvil_file_format, associated text: Maximum build height has been increased to 256 (from 128).
Empty sections of the world are not loaded into memory or saved to disk.
The maximum Block ID has been increased to 4096 (was 256) by adding a 4-bit data layer (similar to how meta data is stored). The rest of Minecraft's code is not currently prepared to take advantage of this, however.
Block ordering has been changed from XZY to YZX in order to improve compression.
Packets for sending chunks have been optimized (a chunk without air is smaller than in the same chunk in the old format, and a chunk with lots of air is even smaller).
Biomes are saved per X,Z column, rather than being calculated on the fly, which means they can be altered by tools; this is useful for map makers. It also prevents bugs where features don't match the biome after changing the terrain algorithm. (Also known as "Biome Shifting")