The notifications are actually pushed from the car itself (to Tesla, then to your phone if I recall correctly), and the setting to enable the notifications is actually stored on the car so it knows to push them to Tesla to push to you.
This is actually similar to how the Chevy Volt's notifications work through OnStar.
This is actually similar to how the Chevy Volt's notifications work through OnStar.