Apologies for the bikeshed, but I have a few comments about the API that might be worth considering before a 1.0 release:

• When a trait represents an action, it is generally named imperatively (Display, Read, Write, Hash, etc.). For least surprise, UnicodeNormalization could be named UnicodeNormalize instead, or perhaps even Normalize, to avoid repeating the module name.
• The method names nfd, nfkd, nfc, and nfkc have no intrinsic meaning, which makes it hard to know what they do in isolation, outside of the context of the UnicodeNormalization docs. Even for a person who is aware of the concept of Unicode normalization, it might not be clear what a line like let c = s.nfc().collect::<String>(); does, without first having seen the documentation, or an explanatory comment. Something like normalize_form_c would at least suggest that some kind of normalization is going on.