A mode S one transmits a 24-bit number which links (via a database) to the aircraft reg.
Actually I think a mode-S transmit the 24-bit unique ICAO aircraft identification (an impossibly long number which nobody uses) *in addition to* the flight ID. (Plus the good old mode A 4-digit code and mode C pressure altitude.) The flight ID for GA is generally the callsign (G-ABCD) but for airliners is their flight number, BA1234 for instance. The GA transponders I know about allow you to change the flight ID yourself without any special equipment, access passwords or anything. In fact, some are too easy to change, and our club has actually send out a warning not to do that because it confuses ATC.
In the early days of mode-S, people were supposedly flying around with flight IDs set to "JESUS" and similar things, greatly confusing ATC when they got their first mode-S scopes.
So I don't think the link works through a database, but rather direct. Although obviously there is a database with all the aircrafts details, including the callsign as painted on the fuselage and the ICAO 24-bit ID. In the UK this database is called G-INFO and maintained by the CAA.
Whether mode-S is required in a country (and if so, under what conditions, at what levels and such) can be found in the AIP of each country. You can find most AIPs at the Eurocontrol site:
EUROCONTROL - The European AIS Database: Introduction to EAD Basic - Home. Need to register, work your way through a number of menus and eventually look for an application called PAMS light. Netherlands looks to be getting ahead the rest of Europe in making mode-S mandatory, but you can still fly in the Netherlands without mode-S. You either have to stay below 1200 ft (which is no significant problem in a country that's below sea level for a large part anyway) or have to get a waiver in advance.
As IO540 said, if you do any significant touring, mode S is a must for all practical purposes. Planning a significant VFR flight throughout Europe without mode S is a major headache. And while you're at it, install an ELT too, for the same reasons.
That Eurocontrol site also does NOTAMs for the whole of Europe, by the way.