Eu não sei exatamente qual passo do guia está errado (ou está faltando), mas você não instalou o pacote para abrir o console mysql de um terminal.
Para trabalhar com o MySQL a partir de um terminal, você precisa instalar o pacote do Cliente . Conforme indicado na sua saída, você pode instalá-lo inserindo este comando:
sudo apt-get install mysql-client-core-5.5
Um ótimo guia, bem escrito, passo a passo e com informações muito úteis é o guia LAMP da comunidade Ubuntu . Se você instalar um componente ou todos os pacotes, esse guia será realmente útil.