O que são esses pacotes?
Considere este exemplo da vida real do que é um pacote: pacotes são o que a UPS entrega à sua porta: exatamente o que você pediu em algum lugar empacotado ordenadamente em uma caixa.
Um pacote do Ubuntu é exatamente isso: uma coleção de itens (scripts, bibliotecas, arquivos de texto, um manifesto, licença, etc) que permitem que você instale um software encomendado de tal forma que o gerenciador de pacotes possa descompactá-lo e colocá-lo em seu sistema.
Eles são como arquivos DLL no Windows?
Não o equivalente a uma DLL seria o que chamamos de biblioteca. Aqueles estarão dentro do pacote.
Onde eles estão salvos no Ubuntu?
Em um diretório em cache. Veja /var/cache/apt/archives/
Que tipos de pacotes existem?
Tecnicamente, há apenas um. Nós usamos arquivos ".deb". Redhat usa ".rpm". Suse usa ".rpm". Nós podemos usar ".rpm" convertendo-o em um ".deb", mas isso é para o usuário mais experiente (eu tenho usado o Ubuntu desde o começo e eu gastei 10 minutos procurando um .deb). Existem outros métodos de instalação, mas os arquivos de instalação que são compactados (como um arquivo .tar) não são um pacote.
Como posso encontrar quais pacotes são necessários para instalar um aplicativo e onde posso encontrá-los?
Você pode usar seu próprio centro de software do Ubuntu para procurar por software baseado em texto. Se você estiver interessado em um método on-line onde você também pode encontrar o pacote de instalação debian e todos os arquivos fonte: ubuntu.packages.com
Lembre-se: tecnicamente, você não precisa saber o que precisa instalar. O próprio sistema sabe o que instalar (incluindo as dependências relacionadas ao pacote que você escolher).
Edite com base nos comentários:
A parte intrigante desta questão começa a mostrar. O android SDK não é um pacote do Ubuntu, então as regras comuns do Ubuntu não se aplicam. É um software de terceiros e é oferecido como um arquivo ZIP geral do Linux. Esses podem ser irritantes, pois muitas vezes dizem apenas que você precisa de outro software. E muitas vezes colocar esses requisitos em um arquivo de texto (um "readme").
Eclipse e Aptana são semelhantes: eles requerem java, mas não o instalam para você. Eles colocam um aviso com o download que você precisa de java. Cabe a você instalar uma versão do java (já que há mais de uma).