I have installed the following packages using apt-get
I added the kernel parameter vga=791 (to enable 1024x768 16-bit framebuffer mode), but although this works (the resolution changes on boot), I still get only the text scrolling past and not the graphical logo.

Is there any step I've missed in setting up the bootsplash in Debian? I'm sure I don't have to recompile the Kernel, or do I?

I'm afraid you do have to recompile the kernel and patch it with the bootsplash patch. Alternatively, try splashy, which doesn't need a patched kernel:

http://splashy.alioth.debian.org/wiki/doku.php

Bootsplash

First you need to recompile your kernel to support bootsplash.

In Debian this is very easy assuming that you are using a newer kernel.

For example for 2.6.17: (this assumes you are in root – I recommend using sux instead of su so you won't have problems with make xconfig - you can of course you fakeroot)

apt-get install linux-source-2.6.17 kernel-package libncurses5-dev libqt3-mt-dev linux-patch-bootsplash

Then
cd /usr/src/
tar -jxf linux-source-2.6.17.tar.bz2
ln -s linux-source-2.6.17 linux
cd linux
sh /usr/src/kernel-patches/all/apply/bootsplash
make oldconfig --> (choose whatever the default is except for bootsplash ->choose Y)
make xconfig --> (Make sure that bootsplash is enabled and you can trim your kernel while your at it if you want)
make-kpkg --initrd --append-to-version=-bootsplash kernel_image kernel_headers

Now you have your kernel image and headers (you should install both if you are going to need to install drivers that require it – like nVidia drivers.)

Finally

apt-get install bootsplash

Let it reconfigure your initrd and your grub.

Now you can reboot.

If you have no picture during your boot make sure that splash=silent vga=791 is at the end of your kernel line.

Ok thanks. I realized that a recompile might be necessary, but was not really sure. By the way, I am quite used to recompiling kernels, but thanks for the "Debian way" instructions. Quite useful to get a re-cap.

Is splashy available in the repository? Because I cannot find it at present in Debian "testing"?

usplash is another one

It's not in the repos yet so you need to download it from the website

It's in unstable. I temporarily pointed to unstable to get it and now it works.