A mi Debian Wheezy le instale el escritorio Gnome 3, y por defecto no vienen los iconos en el escritorio. Para tenerlos se tiene que realizar un simple paso.

Presionamos Fn + Alt + F2 y escribimos lo siguiente:
dconf-editor


Ahora nos dirigimos a org -> gnome -> desktop -> background y hacemos check en check show desktop icons.

Y el resultado es:

Fuente: Joe Steiger