Where does Gnome/Nautilus store directory icons

The meta-data is stored using the meta-data storage system of GIO/GVFS. You can see what attributes are stored on a file by running gvfs-info /path/to/file in a terminal. To have the same folders with the same icons on a different machine, you'll generally have to manually set the icons again. Also note that the custom icons won't show up when browsing the folders remotely via sftp or some similar means.

Take a look in /usr/share/icons.

Gnome stores its icons there.

gio info

Since gvfs-info is outdated, use gio info instead. To get information about a dir/file simple use

gio info /path/to/director/or/file

After invoking this command you will get an output like

...
metadata::custom-icon: file:///home/.../.../myicon.png
...

If you would like the exact full-path name of your icon in a script use something like:

gio info /path/to/director/or/file | awk '/custom-icon/ {print $2}' | cut -c8-

Usage: gio info [OPTION…] LOCATION…

Show information about locations.

Options:
-w, --query-writable : List writable attributes
-f, --filesystem : Get file system info
-a, --attributes=ATTRIBUTES: The attributes to get
-n, --nofollow-symlinks: Don’t follow symbolic links

gio info is similar to the traditional ls utility, but using GIO locations instead of local files: for example, you can use something like smb://server/resource/file.txt as location. File attributes can be specified with their GIO name, e.g. standard::icon, or just by namespace, e.g. unix, or by “*”, which matches all attributes

How to set an icon from command line can be found here.

A complete set of the gio commands can be found on the gnome developer page.