No Ubuntu 9.10 (Karmic Koala) temos 19 wallpapers instalados junto com a distro.

Porém podemos acrescentar mais alguns backgrounds adicionando um pacote de imagens que Kenneth Wilmer disponibilizou em um repositório ppa.

1) Primeiro vamos adicionar o repositório; pelo terminal:

sudo add-apt-repository ppa:kwwii/ppa

2) Agora vamos atualizar o sistema:

sudo apt-get update

3) Baixe o pacotes com os wallpapers com o comando:

sudo apt-get install desktop-backgrounds-extra

Pronto!

Agora basta ir em: Sistema -> Preferências -> Aparência (aba Plano de Fundo) e conferir os seus novos backgrounds.

Fonte: http://www.blogsdna.com/6343/extra-wallpaper-package-for-ubuntu-karmic-koala