Você pode usar apt-show-versions (no pacote com o mesmo nome); executando
apt-show-versions -u
listará todos os pacotes instalados em seu sistema para os quais uma versão mais nova está disponível (usando o banco de dados apt , então você precisa executar apt-get update como mencionou).
Você pode listar pacotes como argumentos para apt-show-versions para limitar a lista apenas a esses pacotes; assim, executando
apt-show-versions -u ${YOUR_WATCHED_PACKAGES}
após apt-get update mostrar as informações que você procura. Você poderia automatizar isso usando Post-Invoke como mencionou.