/usr/share/icons/ typically contains pre-installed themes (shared by all users) ~/.icons/ typically contains folders with the themes installed by the user.

Also, many applications have their icons in /usr/share/pixmaps/ or in the folder with the same name as the application under /usr/share/...

There are several places: (in bracets some examples)

• /usr/share/pixmaps/ ( chromium-browser.png display-im6.q16.xpm firefox.png flash-player-properties.png gimp.xpm gvim.svg texstudio.xpm )
• /usr/share/app-install/icons/ ( adobeflashplugin.png julia.svg texmaker.png thunderbird.png vim.svg vlc.png wine.svg grace.svg)
• ~/.local/share/icons/ ( soffice.png java-lang-thread.png org-jabref-jabrefmain.png) one of the places where Ubuntu searches for icons, if you use relative path
• /usr/share/icons/... and subfolders ( matlab.png .../hicolor/scalable/apps/chromium-browser.svg .../hicolor/scalable/apps/geany.svg .../hicolor/scalable/apps/okular.svgz .../default.kde4/48x48/apps/acroread.png)
• /usr/share/... just subfolders ( .../vlc/vlc.ico .../gimp/2.0/images/gimp-logo.png ) but this one is more for icons used in the program that the logo of the program
• /snap/... just subfolders ( .../inkscape/3080/meta/gui/inkscape.svg .../languagetool/10/snap/gui/icon.png )
• ~/.icons unlikely, that folder exists (but sometimes )

Most of the folders are already announced here, all sources I used:

• https://askubuntu.com/a/6010/676490
• https://askubuntu.com/a/43951/676490
• https://forum.ubuntuusers.de/topic/speicherort-der-desktop-icons/
• Why so many files in /usr/share/app-install/desktop?

As a supplementary for the accepted answer: If you don't find the ~/.icons directory, there may be a ~/.local/share/icons directory instead (PS: My distro is Ubuntu 16.10).