Sim, é possível empacotar um aplicativo .NET como um pacote deb, e você pode dizer que depende do mono para que ele seja instalado se ainda não estiver presente.
A melhor maneira de fazer isso é usar o xbuild para criar seu aplicativo mono. Aqui estão as linhas do meu arquivo de regras debian, para o meu aplicativo mono widemargin
#!/usr/bin/make -f
include /usr/share/cli-common/cli.make
override_dh_auto_build:
xbuild $(CURDIR)/WideMargin.sln /p:Configuration=Release
Em seguida, coloque a seguinte linha no seu arquivo de controle:
Depends: ${cli:Depends}, ${misc:Depends}
Isso automaticamente calculará suas dependências (incluindo mono) e as especificará para você.
O resultado é que quando você instala seu Deb, o mono será instalado se ainda não estiver presente.
Se você precisar de mais ajuda com o pacote debian de aplicativos mono, o melhor lugar para obtê-lo é em # debian-cli no servidor IRC OFTC. Essas são as pessoas responsáveis pelo empacotamento mono no debian e são muito amigáveis e úteis.