Ok, here's my understanding of things. In Linux you have runlevels. Different distributions handle runlevels differently (imagine that). Ubuntu (I haven't tried debian etch yet, but I would guess it's similar) has runlevels 1-5, but runlevels 3-5 are almost identical and X will start in any of them. Back in the old days, runlevel 3 always meant multi-user with no X and runlevel 5 meant multi-user with X. These days it seems everyone wants X so they put it in all the multi-user runlevels. To get around this you need to go into the runlevel that you want to designate as the non-X runlevel and remove the link to gdm. In Ubuntu Edgy, and assuming that you want the runlevel with no X to be 3, you would go to the folder /etc/rc3.d and remove the link S13gdm.
The second part of this was something I was not aware of until today. Ubuntu has moved away from the /etc/inittab model and is using something called Upstart to handle the way runlevels are handled. A nice caveat is that Upstart still respects /etc/inittab, so you can use the good-old-fashioned way of doing things and just create a file called /etc/inittab (if one doesn't already exist) and add the line:
Otherwise you can try using the new Upstart program. Some documentation on that can be found at http://upstart.ubuntu.com/