I suddenly started to get ads in the notification bar. It is probably the most annoying type of ad I have ever seen.
I have just bought a new phone, and had installed a bunch of new apps, so which one was the sinner?
After some googling I found the app AirPush Detector, an app that detects ads like this as they arrive, and tells which app is responsible.
It showed up to be a video editor. When I opened the settings page of the app, I found a setting to turn it off. Voila!