In pervasive environments, privacy is likely to be a major issue for users, and users will want to be notified of potential data capture. To provide notice to users, this paper argues for what it calls labeling protocols, technical mechanisms through which users can be informed of data requests and their consequences. Recent experiences with the Platform for Privacy Preferences Project (P3P), an attempt to provide privacy mechanisms for the Web, suggest important lessons for the design of a next generation labeling protocol that will be usable and useful in pervasive environments. This paper examines the P3P lessons and open issues with an eye to pervasive requirements.