Eu suspeito que você tenha baixado e instalado acidentalmente o pacote do cliente, que não inclui esse binário em particular. Os arquivos .deb do servidor são nomeados no formato chef-server_version_arch.deb.
Eu estava tentando recriar seu problema e acidentalmente fiz a mesma coisa. Se você acessar o link , selecione a guia do servidor do chef. Não parece se destacar.