We need a backend for managing the contents of the watchlist_label_member table, which contains associations between watched items and labels.
On the read side, WatchedItem could encapsulate a label list, which can be optionally populated by WatchedItemStore::getWatchedItemsForUser(). Compare WatchedItem::getExpiry().
Adding and removing a batch of label members could be done in WatchedItemStore by analogy with addWatchBatchForUser and removeWatchBatchForUser. The existing methods take a PageReference[].