If you come from Wear OS 1.0, please note that Wear OS 2.0 changed the way apps get installed on the watch, you now need to install them manually using Play Store on the watch.
Companion apps also have a special way to install on the watch:
If you already have Sleep as Android installed on your phone, then the watch app can be only installed from “apps on your phone” and for some reason not directly from Play Store.
How to get there:
1) Make sure the watch is connected to the phone
2) Go to app list on your watch, select Play Store.
3) Scroll past Recommended for you, Top Free Apps etc., until you see “Apps on your phone”
4) Scroll down until you see Sleep
5) Click the download button to the right. Done!