A assinatura de pacotes nos sistemas Ubuntu / Debian é bastante confusa. Em teoria, a assinatura de um pacote deb permite que a pessoa que recebe seu pacote verifique se o pacote não foi modificado depois que você o assinou. Na realidade, a verificação de assinatura é terrivelmente difícil de configurar e está desativada por padrão. A menos que o usuário faça um monte de configurações localmente, elas não estarão verificando a assinatura quando o pacote estiver instalado.
Para assinar um pacote, você pode usar: debsigs ou dpkg-sig. As assinaturas não são compatíveis umas com as outras, então você precisa ter certeza de que o usuário está usando a ferramenta adequada no lado de recepção para verificar as assinaturas.
O dpkg-sig é mais fácil de usar tanto para você quanto para o usuário, mas debsigs é a ferramenta com suporte embutido (que é desabilitado por padrão) no Ubuntu e Debian.
Eu escrevi uma postagem no blog contendo todos os detalhes técnicos de assinatura e verificação de pacotes fonte (arquivos .dsc), pacotes binários (.deb) e repositórios de pacotes APT: link