The first course of action is to force restart the device by pressing and holding the side button and the Digital Crown at the same time. If you don't see the Apple logo replace the exclamation mark after 10 seconds or so, then the next step is going to an Apple Store and having the device looked at. According to AppleInsider, force restarting didn't work for a lot of affected users -- they had to leave their devices with Geniuses, who had to send them in for servicing since they don't have access to the Watch's diagnostics port. Other people opted to ask for a device exchange when it became clear that force restarting wouldn't work.
Cupertino has yet to reveal why watchOS 3.1.1 bricked some devices. But since the update was supposed to fix a bevy of bugs that affected notifications, messages and other features, Apple will most likely release a patched version that doesn't freeze Watches in the near future.