It is simple. Clone Apple's Messages and ship it on Pixel phones. Make it a download so that people can use it with their Google account on other phones.

The hard part for Google is delivering on end-to-end encryption for messages that don't leave their messaging system (similar to Apple's blue bubbles). They really, really want to see what people are saying to each other.