Debería echar un vistazo a http://www.debian-administration.org/article/Making_scripts_run_at_boot_time_with_Debian
En resumen, con el celeryd guión en /etc/init.d :
$ update-rc.d celeryd defaults
Adding system startup for /etc/init.d/celeryd ...
/etc/rc0.d/K20celeryd -> ../init.d/celeryd
/etc/rc1.d/K20celeryd -> ../init.d/celeryd
/etc/rc6.d/K20celeryd -> ../init.d/celeryd
/etc/rc2.d/S20celeryd -> ../init.d/celeryd
/etc/rc3.d/S20celeryd -> ../init.d/celeryd
/etc/rc4.d/S20celeryd -> ../init.d/celeryd
/etc/rc5.d/S20celeryd -> ../init.d/celeryd