Sim, é seguro.
Ele apenas remove os pacotes que não são mais necessários.
Na verdade, não... ele remove pacotes que foram instalados automaticamente, cuja dependência não existe mais.
Caso prático: quem instala o pacote "build-essential" instala vários pacotes, um deles o pacote "linux-headers-generic". Esse pacote, por sua vez, instala o pacote "linux-headers-<versão corrente do kernel>-generic". Se fizer isso hoje, o pacote instalado será o "linux-headers-3.2.0-44-generic"
Então, ambos os pacotes "linux-headers-generic" e "linux-headers-3.2.0-44-generic" ficam marcados como instalados automaticamente, pois não foi vc que os instalou.
Quando o sistema é atualizado e uma nova versão do kernel é lançada (p.ex., 3.2.0-46-generic), o pacote "linux-headers-generic" é alterado, e passa a depender do pacote "linux-headers-3.2.0-46-generic". Com isso, o pacote "linux-headers-3.2.0-44-generic" fica "órfão", pois ele foi instalado automaticamente, mas ninguém depende dele.
Daí, quando você faz qualquer operação com o apt, ele te avisa: "O pacote linux-headers-3.2.0-44-generic é desnecessário, use o apt-get autoremove para removê-lo".
Mas... imagine que exatamente nessa versão havia um aplicativo (ou um arquivo) que vc usava, e que ainda precisa. Imagine também que a nova versão não inclui mais esse aplicativo/arquivo. Remover o tal pacote pode sim te causar problemas.
Nesses casos em que você não quer que o sistema pense que o tal pacote é desnecessário, você pode marcá-lo como instalado manualmente, com o comando abaixo.
sudo apt-mark unmarkauto <pacote>