If they run the ISPs or can give them orders, they can tell them to null route particular IP addresses -- not properly deliver the traffic to those addresses. By watching the traffic coming out of a mobile device when it's using a particular service, they can easily make a pretty decent list of some of the IP addresses of the servers of that service.
Another possibility is making the ISP's own DNS resolvers refuse to resolve the service's domain name, or making it resolve to something else. Or (at a higher level of sophistication) inspecting DNS queries and blocking those that are related to that service. This is a higher level of sophistication because it is deep packet inspection rather than simply tampering with routing tables or the ISP's own DNS services.
Those are the big ones, and the ways around them are generally proxies, tunnels, and VPNs to get other computers and services that the government isn't yet aware of (or isn't willing to block) to forward the traffic in some way.
Edit: for example, suppose people are using ExampleChat and the government doesn't like that. It can look at the data traffic coming out of a phone running ExampleChat and see that it first looks up chatapi.example.com and that this resolves to 192.0.2.40. Then the phone makes a TCP connection to, say, port 443 of 192.0.2.40. The government-run ISP, or ISPs following government orders, might then start dropping IP traffic to or from 192.0.2.40, or giving wrong results from its own DNS resolver for queries for chatapi.example.com. If they have DPI equipment that is able to look at the content of packets, it could also include searching for "chatapi.example.com" in outbound DNS queries to other nameservers, and dropping those packets or immediately spoofing invalid responses.
This would be pretty effective against ExampleChat because the app simply can't work if it can't talk to the server. If the company rolls out a new version that uses a new name and address, the government could notice the change and block the new one too.