I've ignored the factory-installed Ubuntu distribution that is shipped on the on-board 512mb flash, and instead opted to install Debian GNU/Linux 5.0 ("Lenny") on an external block device.
Advantages for going this route:
As the Sheevaplug is powered by an ARM cpu (armv5tel), the arch of choice is the "new ABI" (EABI) - also known as armel. Previously (before 5.0), Debian's ARM port used the "old-ABI" flavour. (If you have an old Linksys NSLU2 (a.k.a. "Slug") with Debian 4.0, old-ABI would have been the arch you used back then.) In short, the new ABI is a more effecient way of compiling software and using the CPU, and there really are no reason to consider the old ABI any more. In fact, the old ABI has been deprecated, and has already been dropped from the Debian "testing"/"unstable" branches.
Although the 5.0 release of Debian has full support for the armel architecture, it still lacks official support for the "Kirkwood" series which the Sheevaplug is based on. In practice, this means that although all the armel software in the Debian 5.0 distribution is just fine, there is no actual kernel and supporting tools for the hardware included in the standard release. There is also no Debian-Installer pre-cooked. Fortunately, lenny-backports and Martin Michlmayr's Debian for Sheevaplug page provide the missing bits of the puzzle.
Even though there is no installer, getting Debian onto the plug is fairly easy, as long as you have another Linux system readily available. You need either a USB hard drive or memory stick, or an MMC card for the root file system. USB memory sticks are the most painless solution. Using a USB hard drive may need some workarounds (see below) to ensure failsafe booting. Using an MMC needs an updated u-boot bootloader (see below also).
If you're using a USB based device: Simply follow the directions on Martin's page. Download the tarball, unpack on another computer, move the USB device back onto the plug, and connect the serial cable to enter the bootloader to reconfigure it for booting from USB.
If you're using an MMC or SD / SDHC card: Set up a TFTP server to flash the u-boot boot loader according to the appendix at the bottom of Martin's page, then proceed to install as usual. The main advantage of using an MMC is to free up the USB port. (This is particularly important if you later plan to add an USB hub, as I'm unsure whether uboot supports booting USB through a hub) The disadvantage (beyond having to setup TFTP once to upgrade uboot) is that most MMC cards tend to be fairly slow. I'm using a Kingston 4GB SHDC Class 4 card on one plug, and the slowdown compared to a proper USB hard drive is noticeable. Using a Class 6 card may work out better, but those are much more expensive. If you're planning on mounting data drives with nfs or samba while just keeping the actual system files on a local drive, then this won't be much of a big deal at all. See Wikipedia on SD Speed Class Ratings for more info. There used to be a performance problem with the MMC driver but that may have been fixed in recent kernels. There have also been complaints that some brands of cards simply aren't recognized.
Using TFTP Netboot: Haven't tested this, but since the uboot loader seems to support TFTP booting, I assume it would be possible to run in a diskless root-on-NFS configuration as well, as long as you have a server with DHCP, TFTP and NFS server support. Possibly relevant google keywords: "diskless", "netboot", "pxelinux", "root on nfs".
The cyrius.org base filesystem includes a reference to Martin's Orion Repository on people.debian.org/~tbm in /etc/apt/sources.list. You may want to also add the lenny-backports repository to your sources.list, like this: deb http://www.backports.org/debian lenny-backports main In particular, backports contains a slightly newer kernel than the one included.
As announced on the debian-arm mailing list, experimental Linux 2.6.31 armel kirkwood kernels are now available, again thanks to Martin. Update: 2.6.31.1 kernels available.
The u-boot boot loader does not support "raw" linux kernel/initramfs image files. After upgrading kernel .debs, make sure /boot/uImage and /boot/uInitrd files have also been updated. To re-generate these files from the /boot/vmlinuz symlinks, run "flash-kernel". This is a script that will pack the raw files into the format that u-boot expects. Despite its name, there is no flashing of any NAND taking place.
If you want to go the MMC card route but you don't have an MMC reader on your alternate Linux computer, one option is to install onto a USB stick, and then simply copy everything over to the MMC using the Sheevaplug itself.
USB hard drives may take some time to spin up -- long enough that the uboot USB routines fail to detect the drive. When this happens, the "bootcmd" uboot script fails to do its "bootm" command (which executes the kernel), since the ext2load commands failed to put the kernel into RAM, and uboot loader drops back into the interactive shell. This is a problem if you do not have persistent serial console access (which isn't recommended anyway -- there's been several reports in forums of instability with the serial console attached for long periods of time). A workaround is to append ";reset" onto the end of the bootcmd env. This way, if the "bootm" command fails, the uboot loader runs a reset, i.e. the boot is looped -- and by now, the USB hard drive should have had enough time to be spun up properly. See also this page, but do not use those bootcmds directly, as they are designed for a different partitioning scheme.
Although these steps will leave the NAND flash untouched and unused for our purposes, here are some interesting links regarding working with NAND flash on Linux:
Advanced users may want to do a proper debootstrap run instead of simply unpacking a tarball containing the root file system. This ensures you'll start out with an up-to-date root fs from the official repositories, but may need more hacking to get the sheevaplug-specific packages in place. There's a guide on installing debian on the Sheevaplug with debootstrap --foreign, which I haven't tried myself.