Series of facial images from clean-shaven to full beard (Janif et al., 2014)
For the past thirty years, the tendency has been to study sexual attractiveness from the observer's standpoint, i.e., we choose mates on the basis of what's good for us. We therefore unconsciously look for cues that tell us how healthy or fertile a potential mate may be. But what about the standpoint of the person being observed? If you want to be noticed on the mate market, it's in your interest to manipulate any mental algorithm that will make you noticeable, including algorithms that have nothing to do with mating and exist only to keep track of unusual things in the observer's surroundings. If you're more brightly colored or more novel in appearance, you will stand out and thus increase your chances of finding a mate.
We see this with hair color. In one study, men were shown pictures of attractive women and asked to choose the one they most wanted to marry. One series had equal numbers of brunettes and blondes, a second series 1 brunette for every 5 blondes, and a third 1 brunette for every 11 blondes. It turned out that the scarcer the brunettes were in a series, the likelier any one brunette would be chosen (Thelen, 1983). Another study likewise found that Maxim cover girls were disproportionately light blonde or dark brown, and much less often the more usual dark blonde or light brown (Anon, 2008). This novelty effect may be seen in sales of home interior colors over the past half-century: preference for one color rises until satiated, then falls and yields to preference for another (Stansfield & Whitfield, 2005).
The novelty effect seems to apply not only to colors but also to other visible features. In a recent study, participants were shown a series of faces with different degrees of beardedness. A clean-shaven face was preferred to the degree that it was rare, being most appreciated when the other faces had beards. Heavy stubble and full beards were likewise preferred to the degree that they were rare (Janif et al., 2014).
The authors conclude:
Concordant effects of frequency-dependent preferences among men and women might reflect a domain-general effect of novelty. Frost  suggested the variation in female blond, brown and red hair between European populations spread, geographically, from where they first arose, via negative frequency-dependent preferences for novelty. There is some evidence that men's preferences increase for brown hair when it is rare  and for unfamiliar (i.e. novel) female faces . (Janif et al., 2014)
The authors go on to suggest that the quest for novelty may drive the ups and downs of fashion trends. A new fashion will rise sharply in popularity when it is still unfamiliar to most people. As the novelty wears off, its popularity will peak and then decline, especially if it faces competition from a more recent fashion.
There are certainly limits to the novelty effect—something can be novel but also disgusting—but it seems to be more general than previously thought.
Anon. (2008). Maxim's audience prefers brunettes; distribution is bimodal. Gene Expression, July 6, 2008. http://www.gnxp.com/blog/2008/07/maxims-audience-prefers-brunettes.php
Frost P. (2006). European hair and eye color: a case of frequency-dependent sexual selection? Evolution & Human Behavior, 27, 85-103.
Frost, P. (2008). Sexual selection and human geographic variation, Special Issue: Proceedings of the 2nd Annual Meeting of the NorthEastern Evolutionary Psychology Society, Journal of Social, Evolutionary, and Cultural Psychology, 2(4),169-191. http://18.104.22.168/jsec/articles/volume2/issue4/NEEPSfrost.pdf
Janif, Z.J., R.C. Brooks, and B.J. Dixson. (2014). Negative frequency-dependent preferences and variation in male facial hair, Biology Letters, 10, early viewhttp://rsbl.royalsocietypublishing.org/content/10/4/20130958
Little A.C., L.M. DeBruine, B.C. Jones. (2013). Sex differences in attraction to familiar and unfamiliar opposite-sex faces: men prefer novelty and women prefer familiarity, Archives of Sexual Behavior, early view
Stansfield, J., and Whitfield, T.W.A. (2005) Can future colour trends be predicted on the basis of past colour trends? An empirical investigation, Color Research & Application, 30(3), 235-242.
Thelen, T.H. (1983). Minority type human mate preference, Social Biology, 30, 162-180.