AT&T has a link section on their site, Verizon may as well. They actually told me I could call in my IMEI to replace my AW S3 and avoid the activation fee, rather nice of them,
Not sure how the others are, but with Verizon the phone needs the right carrier settings profile in order for the watch to connect. Activation is done through the phone, once that is done the watch will connect to the cellular network. I had some issues with my series 3 last year and it was because the carrier update wasn't coming down correctly.
That being said, this year swapping from the S3 to the S4 was extremely painless. I was expecting a hassle, but a screen popped on on my phone asking me if I wanted to swap devices, hit confirm and boom it was done.