Na página que você vincula, ele diz:
A Canonical fornece este serviço de empacotamento para você gratuitamente.
e continua explicando como preparar o tarball contendo seus binários.
Se você criar um tarball e enviá-lo via MyApps, toda a embalagem será feita para você. Como diz na parte inferior, você pode fornecer um pacote de fontes, se desejar, mas não é obrigatório. Note que isso é específico para aplicativos de código fechado ou pagos, tudo o que é livre e gratuito tem um processo diferente atualmente.
Quanto às suas outras perguntas:
Como a coisa de 32 contra 64 bits é tratada?
Você pode fazer o upload de 32 bits, se quiser, pois isso também funciona em 64 bits. Se você deseja fazer upload de 32 bits e 64 bits, compile-o duas vezes e coloque os resultados nos subdiretórios "i386" e "amd64".
Como o suporte a diferentes versões do Ubuntu é tratado - 10.04, 10.10, 11.04, 11.10, etc?
Você pode especificar em quais versões do Ubuntu seus binários carregados funcionam como parte do processo de envio.
Como as dependências são tratadas? Se, por exemplo, meu aplicativo depende do SDL, como especifico?
Isso será adicionado como parte do processo de embalagem. Se você quiser adicionar um comentário especificando as dependências, isso provavelmente acelerará as coisas.
Se eu não quiser distribuir o código-fonte para o meu aplicativo (que é uma licença proprietária), há uma maneira clara de indicar que a fonte não deve ir com o aplicativo?
Como afirmado, você não precisa fornecer a fonte.
Se eu não estiver usando o autoconf / automake, o meu Makefile precisa ser configurado de uma maneira específica, ou as autotools são necessárias?
Qualquer sistema de compilação suportado no Ubuntu é permitido. Se você estiver usando Makefiles simples, tudo bem. No entanto, se você só fizer o upload de binários, isso não é um problema.