Você precisa de uma barra invertida dupla \
porque a barra invertida única não é apenas o caractere de escape regex, mas também o caractere usado pelo seu shell. Por exemplo. você escapa do ponto, que no nível de shell apenas interpreta em um ponto regular, que é então passado para o apt-get e macha todos os caracteres (como um ponto comum normalmente faz).
Então a resposta é, primeiro a string é interpretada pelo shell, onde a barra invertida tem um significado, e após , ela é passada para o apt-get. O mecanismo de regex do apt-get então interpreta a string pré-processada novamente. Lá, a barra invertida foi substituída (e também tem um significado ligeiramente diferente).
Outra solução é colocar o regex entre aspas, como em:
apt-file search --regexp '.*ssl.*\.so.*'