How do I prevent GDM from running at boot on Ubuntu?

Messing with the runlevel, through /etc/inittab or /etc/event.d (replacement for inittab) or the kernel boot options, won't help. The default runlevel on Ubuntu is 2 (check with the runlevel command), and there is no runlevel which is configured to be multi-user and text mode by default.

Actually, I think your solution

sudo update-rc.d -f gdm remove

should have worked (and it works for me on 8.04)... Is there still a script named something like S30gdm in your /etc/rc2.d folder?

You need to do this:

mv /etc/rc2.d/S30gdm /etc/rc2.d/K70gdm

See, /etc/rc2.d/README. There's README files in all the /etc/rc?.d directories, as well as /etc/init.d.

Edit: The update-rc.d tool is not for editing these links. From the update-rc.d man page:

Please note that this program was designed for use in package maintainer scripts and, accordingly, has only the very limited functionality required by such scripts. System administrators are not encouraged to use update-rc.d to manage runlevels. They should edit the links directly or use runlevel editors such as sysv-rc-conf and bum instead.

Just an answer here for anyone using Ubuntu 10.10+

Using rcconf or sysv-rc-conf to disable gdm will not stop GDM from running on startup.

That is because 'upstart' (http://upstart.ubuntu.com/getting-started.html) is now being used to manage these services.

To disable GDM absolutely, and prevent it from running ever, do this:

sudo mv /etc/init/gdm.conf ~/gdm.conf

(To restore GDM put the file back in /etc/init)

I know this is slightly unrelated, but have you tried the server edition of Ubuntu? I believe it installs without X11 by default, and is a far cleaner base for a server. This also has the added benefit of making it boot really really fast!