How to display "NEW" label in comments list
There is a database table called history that records a users history to check against. There is an option in Views to add a 'new' marker to content that has not been viewed by the user and had been created within a certain time frame. If you are further interested in how the 'new' marker works, you can find the query that Views uses in views/modules/comment/views_handler_field_node_new_comments.inc to add the 'new' tag to a list of fields. 

(edited for clarity)