When composing a new message or a reply you can assign labels or add a star by using the Label drop-down menu in the bottom right of the Compose Window.

This enables you to label or star a message as it is sent and results in that message thread (conversation) being labelled or starred within Gmail.

So a reply will arrive as a pre-labeled for those using conversation view.

Recipients do not see the stars or labels you have added, they are private to your Gmail only.