How does Messages suggest replies?
To my best knowledge, Google has not revealed how it processes the text messages to generate the suggested replies.

Here are a few things which Google shares:
In the Messaging app, the description for Smart reply reads:


  To show you suggestions, Smart reply uses your recent messages but does not store them.


Then, if you follow the Google webpage, the page doesn't reveal much other than:


  Note: You might be charged for data. Check with your carrier for details.


So, at one place Google said that it uses your recent messages. Then, Google also mentions that you might be charged for data. So, I guess it is easy to summarize that the recent messages are transferred to Google servers to understand and suggest replies.

A part of this processing might also be happening locally on the device. But it is hard to imagine everything happening locally in the Google's world. The cloud and the servers are where the real algorithms reside.

Most of Google services are connected together using Google Play Services. So, even if you do not allow Messages to access the internet, Play Services can. And it won't be too hard for messages to communicate with Play Services which then connects to the internet and interpret messages to generate replies.

Note: This is my personal understanding of what I was able to read from Google website. Google has no where explicitly mentioned that it sends your messages to the cloud. They did mention that they at least do not store any messages.