Ok, então foi o que descobri:
As versões mais recentes do Ubuntu usam o upstart (como @polemon apontou corretamente), que usa arquivos de configuração específicos no diretório /etc/init para configurar o nível de execução no qual um script deve ser executado.
O Upstart coloca os arquivos de trabalho do upstart na pasta /etc/init e nos scripts de inicialização normais em /etc/init.d e nas várias pastas /etc/rc*.d e, na verdade, é capaz de executar os dois.
Sistemas que não usam upstart usam somente /etc/init.d e /etc/rc*.d . Neste caso, os runlevels são definidos adicionando um link simbólico ao script na pasta /etc/rc*.d apropriada.
Além disso, aparentemente rc.local executa os scripts no runlevel multiusuário.