Há ótimos tutoriais por aí, por exemplo, este .
Resumindo:
Você cria a estrutura com todos os arquivos e pastas que os pacotes criam e algum tipo de arquivo de configuração (chamado controle) onde você define as dependências, arquiteturas, nome, descrição ...
Depois disso, você constrói o pacote com o dpkg.