I overheard two scoundrels discussing one of their dates as being "coyote ugly".
This comes from the term "coyote date," in which an inebriated person awakens the following morning with a person of the opposite sex in bed. The protagonist's arm is pinned beneath the ugly person's body.
Allegedly, a coyote, when caught in a steel-jawed trap, will gnaw off its own leg to escape.
You can do the math from here.
Other than the popularization of the term from the movie of the same name, I believe it derives from the behavior of coyotes, which (among other canines), when caught in a trap will gnaw off a leg in order to escape death. It describes a person (usually a woman) who is so undesirable that her partner (usually a guy) is willing to gnaw off the limb she is sleeping on in order to escape rather than waking her. The guy will usually find himself in this situation when, after a night of heavy drinking, he wakes up the next morning in the bed of a woman he does not remember meeting and has no desire of getting to know better.
Along with the correct explanations of 'Coyote Ugly', as already provided by The Raven and morganpdx, the whole picture is not complete without giving the three rating levels of the unfortunate date: 'One-bagger', 'Two-bagger', and 'Coyote Ugly'.
One-bagger describes someone so uncomely that they are made to wear a bag over their head so that you don't have to look at their face while copulating.
Two-bagger describes a person who is so much more distasteful that not only do you require them to wear a bag over their head, but you don one yourself in case the bag over their head falls off.
Coyote Ugly, the worst of the three levels, has already been explained.
I would guess it is just as ugly as a coyote. -
Added: In Urban Dictionary there are some posts about the story as posted by The Raven above. The film Coyote Ugly is from 2000. http://www.urbandictionary.com/define.php?term=coyote+ugly
The expression coyote ugly is older, though. From the early 1980s, used among American students for piss ugly. http://dictionary.reference.com/browse/coyote%20?&o=100074&s=t
Google Ngram confirms this student expression. https://books.google.com/ngrams/graph?content=coyote+ugly&year_start=1800&year_end=2000&corpus=15&smoothing=3&share=&direct_url=t1%3B%2Ccoyote%20ugly%3B%2Cc0
So it may be assumed the film took up an expression already in use, but is not the origin of the expression.