Notifications go through Google Firebase servers. This is documented here: https://companion.home-assistant.io/docs/notifications/notification-details/. Your HA server sends the notification to Google, which then sends it to your phone. They don't store the notification they just relay it.
Most mobile apps do something like this. One reason is to improve battery life - your phone can have a single connection to a Google server instead of every app needing its own separate connection.
There used to be a way to use local notifications (meaning you have to be on the same network, either locally or via a VPN), but I can't find the setting any more so maybe it's gone now. (edit: this is still possible)