It's mostly a function of how many kernels you have installed, and the size of their initrds.
For a 3.0 series kernel, initrd runs about 13 MB. For early 2.6 kernels, this was 3.4 MB. So, if you plan on keeping more than a few kernels around, you'll need at least a couple hundred MB.
How much and whether or not this applies to you depends on your use case. If you multi-boot, test kernels, and/or upgrade frequently, you could run out of space on a 100 MB
/boot partition quickly. If you don't do any of these things, it's probably going to be sufficient.
There are very few reasons to skimp on storage (it's cheap, BIOS, mount, and bootloader restrictions on blocks are mostly a thing of the past), and I'm seeing a marked growth in kernel resources with time, so the safe bet would be ~250 MB - 1 GB for now. I still generally prefer a separate /boot partition for control and isolation, though this has almost entirely become a matter of taste (RAID devices would be one obvious exception, LVM and encryption as well as noted by others).