Quão difícil é isso?
Não é tão difícil assim. Eu faço todas as minhas embalagens do zero. Depois de conhecer algumas ferramentas e entender o que está acontecendo, o processo é bastante simples. Esteja preparado para passar algum tempo aprendendo os processos.
Preciso criar meu próprio repositório para que isso funcione?
Um repositório (como um PPA) é para publicar seu pacote no mundo todo. Então, sim, se você quer que as pessoas possam instalar o pacote, você precisa incluí-lo no Debian / Ubuntu, ou você precisa publicá-lo em um repositório.
Os PPAs também têm acesso ao farm de construção do Launchpad, para que eles possam criar pacotes binários a partir de pacotes de origem. Mas você pode fazer isso localmente também. E, enquanto empacota algo, você realmente quer testar localmente, em vez de esperar que o LP compile seu pacote (as filas de construção do LP podem durar horas).
Eu preciso assiná-lo com minha chave pública ou algo assim?
Se você deseja fazer o upload para um PPA, é necessário assinar seu pacote de origem com sua chave privada.
Um pacote deb funcionará para todas as distribuições baseadas no Debian, ou eu preciso construir uma versão separada para cada versão?
A resposta segura é não. Mas às vezes é bastante simples produzir uma vez deb que funcionará em todos os lançamentos Debian e Ubuntu atuais. Depende do pacote e da toolchain que você usou.
Sugiro: