They didn't. They _sued_ Google, trying force them to link to them (and, naturally, pay for it – a paltry 6% of Google's revenue in Germany¹). It was turned down by the courts in September², only then was Google given a gratis license by some publishers.
Smaller actors (other search engines, newspapers, bloggers, …), of course, can't afford risking such a confrontation and now have to pay up for the privilege! of being allowed to advertise for Axel Springer publications.
This, too, ended up in the courts, as said smaller actors sued the publishers over the gratis license given to Google, claiming it was anti-competitive. The case is handled in secret, VG Media (the organisation founded by AS to handle licensing) is suppressing information of it from becoming public.³
¹: http://www.heise.de/newsticker/meldung/Leistungsschutzrecht-...
²: http://www.bundeskartellamt.de/SharedDocs/Meldung/DE/Pressem...
³: http://www.golem.de/news/gratislizenz-fuer-google-die-streng...
Very much off-topic, but your punctuation error left me wishing English allowed for infixed exclamation marks. This would place emphasis on the word 'privilege' rather than on the whole phrase (as the case when appended to the end of a sentence).