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 (
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.
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.