The same way that Element does - they host a service for you that relays push notifications their Firebase Cloud Messaging endpoint for Android or iOS Instant Notifications for Apple. I believe ntfy's hosted option is the way they offset the costs of hosting this, even if self-hosted options can take advantage of those servers free of charge.

I think it's reasonable for Zulip to ask for compensation for access to these gateways, since Apple and Google do not make them available to end users free of charge, and the burden of responsibility to ensure that these systems aren't abused is on them. Also, the fact that they offer mobile push notifications for any self hosted server of up to 10 users is pretty generous, and there seems to be a Community plan option for larger servers that includes "groups of friends" as a qualifier. It really seems they're offering quite a bit.

This isn't true, self-hosted Android push notifications in ntfy are provided using a "foreground service" by default (i.e: the app keeps a websocket open and listens), unless you set up firebase for yourself and build a custom version of the app with the cert baked in.

https://docs.ntfy.sh/subscribe/phone/#instant-delivery