A long time ago I found information about installing ubifs on the Sheevaplug.
However, it used a non-Debian kernel. This port describes the steps to boot from a regular Debian kernel.

The information used is found here, here, here and here.

$ dpkg-reconfigure linux-image-2.6.32-5-kirkwood
A warning is issued about the name of the root device ubi0:rootfs
$ flash-kernel
It doesn’t write to the flash memory, but generates /boot/uImage and /boot/uInitrd

The following environment is used in U-Boot (version 2011.12):

baudrate=115200
bootargs=console=ttyS0,115200 mtdparts=orion_nand:512k(uboot),4m@1m(kernel),507m@5m(rootfs) rw ubi.mtd=2 root=ubi0:rootfs rootfstype=ubifs
bootcmd=run bootubi
bootdelay=3
bootnand=${x_bootcmd_kernel}; setenv bootargs ${x_bootargs} ${x_bootargs_root}; ${x_bootcmd_usb}; ${x_bootcmd_sata}; bootm 0x6400000;
bootubi=run x_bootcmd_ubi; run x_bootcmd_regular; setenv bootargs ${x_bootargs} ${x_bootargs_root}; bootm 0x800000 0x1100000;
ethact=egiga0
ethaddr=XX:XX:XX:XX:XX:XX
mtddevname=uImage
mtddevnum=0
mtdids=nand0=orion_nand
mtdparts=mtdparts=orion_nand:0x400000@0x100000(uImage),0x1fb00000@0x0500000(rootfs)
partition=nand0,0
stderr=serial
stdin=serial
stdout=serial
x_bootargs=console=ttyS0,115200 mtdparts=orion_nand:512k(uboot),4m@1m(kernel),507m@5m(rootfs) rw
x_bootargs_root=ubi.mtd=2 root=ubi0:rootfs rootfstype=ubifs
x_bootcmd_kernel=nand read 0x6400000 0x100000 0x400000
x_bootcmd_regular=setenv mainlineLinux yes; setenv arcNumber 2097;
x_bootcmd_sata=ide reset;
x_bootcmd_ubi=ubi part nand0,1; ubifsmount rootfs; ubifsload 0x800000 /boot/uImage; ubifsload 0x1100000 /boot/uInitrd;
x_bootcmd_usb=usb start;
In order to use the setenv command, the $ and ; must be escaped with a backslash.The highlighted parts are the parts I needed for a correct boot.