Many animals not only have an understanding of beauty in the sense of sex appeal, there is significant overlap between what animals find attractive and what humans find attractive.
Symmetry (for animals that are "supposed" to be symmetrical) and smooth, even, or shiny skin/fur/feathers/scales/exoskeleton are all characteristics that indicate health, fitness, and lack of parasites. While (most) humans don't find non-humans sexually attractive, we can often tell the difference between a beautiful specimen of a species and an ugly one, and that will often reflect the preferences of other members of that animal's species.
We can even apply the same airbrush and Photoshop techniques used for human models on animals to make them look better - for instance, the "Ridiculously Photogenic Horse" meme. Also, chickens are known to find physically attractive humans more appealing.
Many species, including humans, also find bright colors attractive. Not only does it catch the eye, it is an indicator of good health, since it is difficult to produce bright pigments when sick. Even though our natural coloration is uninteresting compared to, say, birds, we wear colorful clothing and jewelry to enhance this. Brightly colored eyes are also seen as appealing.
Humans also find animals with graceful, controlled movement more appealing than those with short, twitchy motions, likely for similar reasons: jerky movements in humans and related species is an indicator of disease, injury, or fear. The smooth undulation of an eel or whale is preferred to the twitchiness of mice, birds, or insects.
Species humans find beautiful often have these characteristics. Peacocks, parrots, butterflies and tropical fish are traditionally "decorative" animals thanks to their bright colors, and many people find the sleek fur and grace of deer and big cats attractive. Even species that are not culturally seen as beautiful can be appealing to some: the shiny, iridescent scales and smooth undulations of a healthy snake, or the striking black exoskeleton of a spider. It isn't for nothing that these particular creatures are often associated with sexuality.