I can document how I installed Debian here, no problem.

I found the easiest way was to use mgillespie's "Alternative Debian Install Method". For starters, I made sure I had enough room on my plug to install everything mgillespie's script required; you can also install onto a USB disk or flash drive, I just chose to use internal NAND, as I would be erasing everything soon.
1. Download mgillespie's script and place it in a directory of your choice. See
THIS thread for reference.
2. Execute the script:
sudo bash ./DebianSheeva1-5.sh
3. Wait for the script to finish building a rootfs.tar.gz
4. Replace the old Ubuntu rootfs.tar.gz in the SheevaPlug Installer 1.0 with your newly created Debian rootfs.tar.gz
5. Run through the normal SheevaPlug Installer procedure
That is the basic install procedure I followed. I used mgillespie's README file and the documentation on the SheevaPlug Installer to get me through the rest, but the whole process took about 20 minutes from running the script to getting an SSH tunnel up and running.
One interesting aspect of all of this (to me anyway) was that I was able to install the sheeva-with-linux kernels after issuing:
sudo apt-get install devio
Once devio was installed, I could then update my kernel as if I were using the stock Ubuntu install: sudo bash ./README-2.6.32.9 --nandkernel
Hope this helps!