Na busca do Ubuntu Software Center por openssh-server, ou então abra o terminal e digite:
sudo apt-get install openssh-server
Se isso não funcionar, abra o Ubuntu Software Center e navegue até Editar - > Fontes de software - > Ubuntu Software , e certifique-se de que você tem, pelo menos, os repositórios principal, universo e multiverso marcados com uma marca de seleção.