Labels help you organize your messages into categories. The advantage of labels over "folders" is that more than one label can be assigned to a message. Labels can also be created with sub-labels, in order to create a hierarchy.
Labels are only visible to you. The sender will never know what you've labeled their message (unless you tell them).
Labels can automatically be added to a conversation via filters. (See: gmail-filters)
Gmail supports a maximum of 5,000 labels.