Obviously, it's not. According to this article, watchOS 3 is for sure out. The paired iPhone is an American (just to rule out possibility of any regional differences) iPhone 6s running iOS 10.0.1. I've tried opening and closing the app, restarting my iPhone, clearing RAM (by holding the power button down until the Slide To Power Off appears, then holding down the home button)---nothing. This iPhone was in the Beta Seed Program, but I just deleted that profile and restarted the iPhone just in case. Still doesn't work. Also, my internet connection is good enough (LTE at 5 mbps), so that shouldn't prevent it from at least searching for the update. I'm out of ideas here. Is there something I can do to resolve this now?
This is typical and usual at major OS launches for short windows of time after release. Apple has hundreds to thousands of update servers and they roll out the announcement of the update progressively.
It is highly disruptive to get a stalled download since that uses CPU and battery - so preventing 10 downloads when the servers can only accommodate 2 makes each update go more smoothly once it starts.
I've not seen the slowness take more than 8 to 20 hours to level out - so if you are locked out for 2 days or more, you might contact support and/or try a different network connection.
If you want to try restarting the watch and the phone, perhaps that will jog a full check.