Based on discoveries of art, burial, and other evidence for ritualistic beliefs associated with hominid fossils, it seems likely that anatomically modern Homo sapiens, around 125,000 years ago, was able of comprehending abstract concepts like beauty. It's possible that earlier hominids were also aware of aesthetics, but fossil evidence for abstract thought is a bit sketchier. The fact that other non-human primates (such as gorillas) seem to understand abstract concepts may suggest an earlier origin.
The evolutionary basis for aesthetics is probably not a direct selective pressure, but rather is an indirect consequence of the behavioral evolution associated with living in social groups. Much of our behavior (such as altruism, kindness, jealousy, etc) evolved to promote and facilitate social cohesion and the ability to understand abstract concepts, and especially to empathize and understand feelings and motivation of other humans, would have been very important for those situations.
As for other animals, that may be more difficult to tell because of our tendency to anthropomorphize their behavior. I would guess the answer is no, except for other higher primates.
-MEC