When Messages receives an iMessage, it matches the source with an entry in your Contacts. If you don't have a matching contact, you just see the phone number or email address of their iCloud account.
If your phone syncs its contacts to iCloud, Facebook or some other source, and you would like your contacts on your computer to also sync to this source, open System Preferences then choose Internet Accounts. If you use iCloud for syncing, choose iCloud from the list of accounts then tick the "Contacts" checkbox. If you use Facebook, add a new Facebook account and your friends list's contact information will download and stay up-to-date as they change it. Pretty much any other source of contacts you can think of can be added here, either through one of the main account types for the major providers or "Add Other Account" for standards-based things like LDAP & CardDAV.
Wait a few seconds after adding the new account and ensuring "Contacts" is checked off, and your iMessages should now match up names where there were phone numbers or email addresses before.
While you're in Internet Accounts, you can also add certain other message sources to Messages, if you desire. As an example, you can add a Google account and tick the "Messages" checkbox, and then your Google Talk messages will appear inside of Messages alongside your iMessages. AIM, Yahoo! and Jabber round out the other options; no Facebook yet.
There are a number of other routes to access your Messages and Contacts sources (namely via the iCloud preference pane or via the "Accounts" tabs present in each app's preferences) but Internet Accounts is the one-stop source for all of this. Each different route controls the same information, back here in the master source.
Best Answer
This answer's a bit late, but I finally figured out the issue.
Your Apple Watch's contact list is most likely out of sync with your iPhone.
Try checking your Apple Watch's contact list though the phone app. If it looks like some contacts are missing, it's likely that the contact list isn't synced properly.
The easiest way to manually re-sync your contact list is to create a dummy contact "AAAAA" on your iPhone. Once it's been resynced, all your contacts should start displaying properly again.