Ok, I was going to post this as a question or "HELP ME". But I fixed it. Since I already wrote down all the problems I had I will post them anyway for all the other poor guys in my situation as a reference.
I was going to install Debian on my SD Card using the tutorial from tbm (cyrius.com).
I checked which u-boot version I had and since it was too old I had to upgrade it. I used the "USB stick method" from the same site using WinXP.
Somehow this went terribly wrong. I guess the USB Stick was faulty (although it was recognized). So the Sheevaplug won't boot up and I had no access via the serial port (the screen stayed black after pressing Enter several times). The green LED was on, the blue LED was off.
So I read this tutorial to "unbrick" it: http://plugcomputer.org/plugwiki/index.php/SheevaPlug_Installer
I'm not using minicom so the "bug" section does not apply for me.
It seems my plug is older than July so I had no problems recognizing it, I also skipped the section.
I used a brand new USB Stick from Transcend to make sure this time nothing goes wrong because of the USB Stick. I have copied all the files to the root as told in the tutorial and put it in the Sheevaplug. I started it and on XP I ran: runme.exe nand from the command prompt.
After some command action the important lines should be:
successfully erased blocks 5 to 6 and NAND flash[...]
wrote file uboot-dev.bin to NAND flash 0 up to offset 0x000c0000 in 20s.
successfully erased blocks 0 to 4 and NAND flash[...]
wrote file uboot.bin to NAND flash 0 up to offset 0x00074000 in 75s.
The green LED is on and so is the blue LED.
So far so good.
At the beginning of this procedure it is said to unplug and replug the minisusb cable after uboot.bin is written. The same is stated in the tutorial "Afterwards the Windows version beeps; you need to unplug your mini usb cable, plug it back again and open the terminal[...]"
My first problem is, there is no beep. So I thought "it is said... 'after uboot.bin is written...' " which obviously is the case - I unplugged the miniusb. There was the standard windows sound which occures after inserting or removing USB devices (is this meant by beep?). But then the command line of Windows was flooded by communication error messages. I used CTRL+C to exit it and tried to connect with Putty. Still the same black screen I had directly after the brick.
I started all over starting with "runme.exe nand" but this time I waited 10 minutes after "wrote file uboot.bin" and still no beep. So I unplugged the mini usb cable again and it's the same error message flood. This time I did not exit the command line but tried to connect with putty. It worked but there was the same message flood with unreadable characters. Looked like a wrong encoding, so nothing readable.
I started all over again... and this time I waited more than 30 minutes. There were 2 addition lines after 30 minutes: "Error: invalid mode value encountered 0" and "Error: cpsr contains invalid mode value - communication failed". After 5 more minutes it continued with "[...]cpsr: 0xffffffff pc: 0xffffffe9"
and again both of the errors.
After the last lines (I guess the sheeva was on for 45 minutes) I cancelled the command line again (with CTRL+C) and unplugged/replugged the miniusb. This time putty worked (after pressing the Enter key once - didn't work before!). Everything is back to normal - and with the latest uboot I intended to install (and because the Sheevaplug bricked).