Is there evidence that some non-human species perform sexual selection based primarily on intelligence? How do they do this?
Very intresting question. The problem is that animal intelligence is hard to measure not only for scientists, but probably also for the potential mate. Paradoxically, that is why selection for intelligence, if it occurred, may be very strong. One has to be smart in order to recognise smart behaviour, so preference and preferred feature are strongly connected. But that's only my opinion.

Boogert et al., 2011 1 reviews the current knowledge about animal preferences for cognition skills. They conclude that there is very little data on this subject. The given examples are:

1) Preference for elaborating birds songs (as songs are not inborn and have to be learned)

2) Spatial abilities: 


  In meadow voles (Microtus pennsylvanicus), males with better spatial learning and memory abilities were not only found to have larger home ranges and to locate more females in the field (Spritzer, Solomon, et al. 2005 2) but were also preferred by females in mate-choice tests, even though the females did not observe males’ performance on spatial tests (Spritzer, Meikle, et al. 2005 3).
  
  In guppies (Poecilia reticulata), males that learned faster to swim through mazes to gain a food reward were found to be more attractive to females (Shohet and Watt 2009 4). However, females were not able to see the males’ performance in the mazes. Although male learning ability was weakly correlated with saturation of the orange patches on his body (a sexually selected trait (...)), orange saturation surprisingly did not correlate with female preferences. Thus, the cues leading female guppies to prefer faster learners are unknown.


It is possible, that females base their choose on some factors that correlates with cognitive skills or on total wellness, what may depend on intelligence.

3) bowerbird's abilities to build bowers (courtship constructions):


  Comparative studies across bowerbird species have shown that relative brain size is larger in species that build bowers than in closely related nonbuilding species (Madden 2001 5). In addition, relative brain size increases with the species-typical complexity of the bower (Madden 2001 5), and a comparative study on the relative size of specific brain regions showed that species with more complex bowers have a relatively larger cerebellum (Day et al. 2005 6).


4) foraging performance


  A recent experiment by Snowberg and Benkman (2009) 7 using red crossbills (Loxia curvirostra) showed that, after observing 2 males extracting seeds from conifer cones, females associated preferentially with the more efficient forager of the 2. The authors were able to exclude female choice for correlated traits by experimentally manipulating foraging efficiency, such that fewer seeds were available in the cones of one of the males. The males were also swapped between treatments (i.e., slow vs. fast forager) so that male identity could not explain the females’ preferences for the most efficient forager.




Another way that intelligence may be favored by sexual selection is "cheating" during courtship. For example most frog species call to attract females. But this signal may also attract aggresive rivals or predators. Some males, especially the weaker ones, do not call  but stay near calling individual.  This allows them to avoid confrontation and wait for approaching females [8]. The successfulness of this strategy may depend on how "smart" the individual is (only my opinion).

[1] Boogert, N. J., Fawcett, T. W., &amp; Lefebvre, L. (2011). Mate choice for cognitive traits: a review of the evidence in nonhuman vertebrates. Behavioral Ecology, 22(3), 447-459.

[2] Spritzer MD, Solomon NG, Meikle DB. 2005. Influence of scramble competition for mates upon the spatial ability of male meadow voles. Anim Behav. 69:375–386.

[3] Spritzer MD, Meikle DB, Solomon NG. 2005. Female choice based on male spatial ability and aggressiveness among meadow voles. Anim Behav. 69:1121–1130.

[4] Shohet AJ, Watt PJ. 2009. Female guppies Poecilia reticulata prefer males that can learn fast. J Fish Biol. 75:1323–1330.

[5] Madden J. 2001. Sex, bowers and brains. Proc R Soc Lond B Biol Sci. 268:833–838.

[6] Day LB, Westcott DA, Olster DH. 2005. Evolution of bower complexity and cerebellum size in bowerbirds. Brain Behav Evol. 66:62–72

[7] Snowberg LK, Benkman CW. 2009. Mate choice based on a key ecological performance trait. J Evol Biol. 22:762–769.

[8] Bateson P. 1985. Mate choice. Cambridge University Press. 181-210