unlaced-snarl-good OK, it seems you won't see the messaging app in the App Store. At least for now. Here's a quote from the GrapheneOS chat by the project account:
grapheneos: this is only for fully supported devices on a recent OS release
As of today, fully supported devices means Pixel 6 and up.
For those who will come here later, if you can't see an app in the App Store, check if it's enabled {Settings -> Apps -> See all -> 3 dots menu -> Show system -> App name -> Enable). Once you enable it back, it should appear in the App Store.
Do not disable system apps.