How can a script add a little icon overlay on files' icons

If you look at the reference Icons and Icon Overlays or more specifically How to Create Icon Handlers and How to Implement Icon Overlay Handlers you will see that you need to implement a DLL/COM Component.

Said DLL needs to implement certain interfaces (IUnknown and IShellIconOverlayIdentifier as far as I can tell) and will be called by the Windows explorer process upon displaying an icon. For this to happen you need to create an entry in the registry. As you probably want that overlay to be displayed for all types of files you will probably need to register for a general file type.

Later on GetOverlayInfo will be called to register your icon and IsMemberOf to indicate whenever or not you want your overlay to be displayed.

As for identifying files or storing information about them you could use an Alternate Data Stream though that would mean it would only/mostly work for NTFS and as you said is not really part of your question.

If you look at this help article for DropBox you will see that the registry key HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\ShellIconOverlayIdentifiers could/would also be important in order to decide which icons are going to be displayed.