Sobre a pasta icons
O único programa que possui ícones em ~/.local/share/icons
é Wine, então não, uma instalação padrão não deve criar a pasta.
A maioria dos programas instalados coloca seus ícones em /usr/share/icons
, onde todos os usuários podem acessá-los.
Sobre o arquivo .desktop
Eu fui em frente e criei, e o resto das pastas mencionadas na resposta,
~/.local/share/icons/hicolor/16x16/
etc.
O ícone deve ser colocado em uma pasta chamada ~/.local/share/icons/hicolor/16x16/apps/
.