I run a small lab of Macs using the multiple-user logon. The preferences and files for each user are stored on a server, but I believe when using a single machine you will find them in a folder called "Users". Each person will have a their own folders inside that one for Apple Menu Items, Desktop Picturees, etc.
You will find a folder called Internet Search Sites which contains the Sherlock plugins. I was unable to get System 9 to copy these for each user and so I had to manually drag the same folder for one User folder to another (holding down the option key so that it copied rather than simply moved).
Adding sites, then, is simply a matter of dragging them into the folders. I don't recommend just dopping them into the Sherlock window.
Hope this helps.