TL;DR: By December 6th, 2018, Google stopped serving Nearby Notifications. Android users won't receiving this kind of notifications.
How were they able to push a notification?
As @Martin Fürholz pointed out, that was came from Google Maps notification service. Specifically, from Nearby Notifications feature that being developing by Google for the last years.
Nearby Notifications Overview:
Nearby Notifications helps users to discover what's around them, by surfacing location-specific notifications for apps and websites, with no prior app install required. Using Nearby Notifications, you can:
- Drive your own app installs.
- Open personal or business profiles in social apps.
- Launch conversations or chatbots inside messaging apps.
- Drive consumers to content about nearby products.
- Help users explore store inventory.
- Drive checkins, reviews within local/travel apps.
Neither experience requires that an app is installed on the user's device.
(source)
How Nearby works:
Nearby can use small amounts of Wi-Fi or mobile data to connect to Google and get info about broadcasts or shared apps.
Nearby doesn’t track, monitor, or send personal info from your phone.
- Nearby broadcasts are one-way, like over-the-air TV or radio.
Services that send Nearby signals don’t detect or get data from your
phone.
- When you give permission, apps that work with Nearby share
with each other using remote servers. The sharing devices don’t
connect directly.
(source)
How to disable Nearby Notifications?
- Open your phone’s Settings app
- Tap Google > Nearby > Settings
- Under "Notification categories," tap a category.
- Turn that notification type off.
(source)
Related articles:
But, keep in mind, Google decided to discontinue support for Nearby Notifications. They'll stop serving Nearby Notifications on
December 6th, 2018.
Learn more.