Isso deve funcionar ..
sudo update-rc.d ssh defaults
EDITAR:
Se a sua rede estiver configurada com o Network Manager, a conexão não será estabelecida até que o usuário faça o login através da GUI. Para configurar manualmente você tem que editar o arquivo /etc/network/interfaces
, dê uma olhada em este guia e se você usa wireless você pode ter um olhe aqui