Add labels on replying to a post

One of the ways to do it would be 

to capture the post submit method via jQuery 

write a function to get the reply message's id and use it in a REST call to edit the message and add label.

Something like "/messages/id/261/edit with parameter label.labels

Editing a message, would return the message node as its response.

However if you are going to do this for a lot of messages at a time on page load , there might be some trade off with performance.

Another method could be to check if you can use tags in a reply ,and restrict tags to your list of labels.

samudhraa is likely correct, and I give Kudos for a clever idea; however, I'm not sure that I would recommend adding labels to replies via the REST API. Labels are really intended to categorize the overall discussion, so you could get an inconsistent user experience. If you anticipate needing to categorize a reply differently than a topic message, that would probably be a better use case for tags.

As samudhraa also suggested, if you were thinking of labels because you liked the pre-defined nature or the idea of restricting which labels were used, you could likely do a customization with tags to acheive a similar approach.