Just open your app drawer, find the Messenger app, tap and hold on it, and drag back to your home screen or shortcuts!
UPDATE: I didn't notice this was in a smartwatch forum! Sorry! This applies only to a phone! On the watch you should check the Play Store on your watch or on your phone (making sure you select WATCH) to see if the app is still installed (and if it isn't, re-install it). If it is installed, scroll through the app list on your watch as it might have moved around.