For the benefit of other newbies struggling to cross-compile applications on a Linux PC for the SheevaPlug, I made two mistakes in the post above:
1. The Plug_Host_SWsupportPackageLinuxHost.zip contains two compiled file: gcc.tar.bz2 is indeed a Bz2 file, but "Linux Host Filesystem - rootfs.tar.bz2" is actually a gzip file. I ran this:
mv "Linux Host Filesystem - rootfs.tar.bz2" rootfs.tar.gz ; tar xzvf rootfs.tar.gz
2. To compile a basic app like "Hello, world", cd to LinuxHost/gcc/bin, and run "arm-none-linux-gnueabi-gcc -o hello hello.c", which will create a binary that uses shared libraries.
At this point, I'm surprised it works although I didn't specify neither the path to the C library nor its name. Maybe Marvell's toolchain is hard-linked to figure this out by itself by reading files from LinuxHost/rootfsv1.0.