On Android there's a nice open source backup tool written by the cool folks at The Calyx Institute, called SeedVault. It backs up your apps and all of their settings, and re-installs your settings when you re-install an app. It's cool, it's good.

You can store your backups in a few different places: the phone, a usb stick plugged into the phone and Nextcloud.

On CalyxOS, GrapheneOS and LineageOS there is a section of the install process that offers to let you restore from your Seedvault backup. However, you don't have Nextcloud installed yet when you're at that part of the install. The installer promises to let you install Nextcloud, but it seems to try to do that using Google Play, which you don't have. So instead it just crashes. And when you continue the install you can no longer restore from the back-up -- going into the settings and selecting Backups starts the process of creating new backups.

So, here's the process:

1. Install GrapheneOS
2. Skip restoring from backup
3. Download and install F-Droid
4. Install Nextcloud from F-Droid
5. Log into Nextcloud
6. Enable Developer Options on your phone
7. Enable USB Debugging, and allow your phone
8. From computer: adb shell am start-activity -a com.stevesoltys.seedvault.RESTORE_BACKUP
9. On the phone: tap Nextcloud
10. Watch "Looking for backups" for a while
11. SeedVault appears to exit, but do this again: adb shell am start-activity -a com.stevesoltys.seedvault.RESTORE_BACKUP
12. Now you should be able to enter your backup passphrase and enjoy all your apps coming home again