This seems to have been asked by
JRA-14425 back in 2008, but at the time the Labels were a separate plugin, and I wasn't able to find whether this had been resolved as the links went to the LBL project, which I suppose was removed when the labels were included in the base JIRA software.
We are using JIRA 4.1.2, so if this has been fixed in a more recent release, that is fine too, but at the moment it isn't working as described in the documentation.
Our organization's usage prevents us from being able to give every user 'edit issue' permission (right now there are 5 people who have edit permission), but we would like to be able to broaden the scope of who is able to label issues (everyone would work, or even just have a separate permission we can add project roles to).
In the documentation there was no mention of any permission settings for the ability to edit/add/remove labels from issues, but I found the previously mentioned
JRA-14425 which suggested that the permission was tied to the edit issue (which we've had to restrict). This is consistent with the behavior we have seen here (those without the edit issue permission cannot add/edit/remove labels).