You'll need to unpair it from your current phone (which will backup the watch to the phone) . Then backup the phone. Restore the phone backup to your new phone. Finally pair the watch to your new phone.
Also worth noting that if you want to keep all your health data and activity history the phone backup needs to be an encrypted backup via iTunes.
If you are not bothered about keeping all the old settings then just unpair from current phone and then pair to the new one.
Dang that is such a hassle, do messages not return after restoring a backup? Cuz I remembered the last time I restored my watch I lost all my messages on it and some data.
I'm slightly confused, does unpairing reset and wipe the watch?
Do an encrypted backup so your health data is maintained.
No - per Apple, health data is backed up via iCloud too. Your health data should be synced with your iPhone.Ah darn, that's why I lost so much data. The only way to keep everything is through iTunes?