Where are the .desktop icon files stored?

The .desktop link files are stored in /usr/share/applications for software installed for all users, and $HOME/.local/share/applications for things you have installed only for yourself.

The actual icon (image) files are a bit more scattered (since a .desktop file can specify their absolute path), but /usr/share/pixmaps and /usr/share/icons contain a good fraction of them. (icons at $prefix/share/icons/ with required fall-back version in hicolor theme can be loaded without the full path, thus such as Icon=video-display where $prefix can be /usr, /usr/local or ~/.local; See specification at freedesktop.org: Icon Theme Specification )