I'm designing an embedded Linux board for use as a web-based controller. It will be based around an Atmel AT91SAM9G20, which uses an ARM926EJ-S core. Anyone have particularly good or bad experiences with bootloaders? More broadly, how should I go about building/choosing a Linux distribution for this board?
Both the bootloader and Linux distribution depend on what your final application is.
RedBoot and uBoot are both popular bootloaders for embedded Linux. They support writing to flash, loading code over serial/ethernet etc. But, for a deeply embedded device, a very minimal loader might be better, leaving everything else to linux.
If you need access to a lot of software packages, you might try Debian's ARM port. For anything else, I'd recommend OpenEmbedded or Buildroot - both are configurable build systems for generating linux kernels and filesystems with only what you need and nothing else in.
I think your best bet for bootloader is U-Boot It has a port for the processor you're looking for in it's "arch" folder, and it's probably one of the most popular bootloaders. You might look into the atmel board folder of the source for an idea on how to configure your code around your chip.
I've used U-Boot before and it is quite good, very flexible. You should contact Atmel to see what SDKs they offer. If you have the space in Flash then Debian is a good choice. It's pretty large but being able to install a package with a simple "apt-get" is much easier than having to try and cross compile it yourself. I use the TIAM335x for my projects and people in the BeagleBone community have even made available tar archives of Debian already cross compiled for the ARM. Installing the root filesystem is then as simple as untarring the provided archive.
I have not much experience with bootloaders, but I can answer this question:
How should I go about building/choosing a Linux distribution for this board?
You should definitely use Debian as base of your system, because it's the most versatile Linux ever. It has a large package (application) collection for ARM and other architectures.
There are some distributions dedicated for ARM, but after 3 years of messing around with devices like Raspberry, BeagleBone etc. - I feel Debian has more packages working on ARM than ARM-specialized distros.