It might be interesting to add that the prefix "con" gives a clue to the most important difference between these terms. A word accumulates its connotive meaning from past uses in past contexts--take, for example, the words "prejudice" and "discrimination". Once perfectly legitimate terms to some steps in the logical progress, their use in social contexts has rendered them tainted for non-social use--if I said I was prejudiced against Indian food, for example, I would not be communicating well. Some words get a connotation from a "frozen idiom". We used to be able to call a female dog a bitch, but because of the frozen idiom "son of a bitch" (meaning "he's a dog" or "less than a human") the word has taken on connotations that prohibit its use in other contexts.
In literature, denotation refers to the literal meaning of a word. Connotation, on the other hand, is more complex. It refers to the deeper meaning that a word carries beyond its literal meaning. These meanings and associations are culturally determined. For example, a "chicken" is obviously a barnyard fowl. But if one describes a person as a "chicken" they are using a word that carries connotations of cowardice. To use a slightly more subtle example, in referring to the human body, "thin" and "skinny" denote essentially the same thing. They refer to a slender person. But "skinny" carries an unhealthy, or at least an unattractive connotation, whereas "thin" is more positive.
Denotation is the dictionary definition of the word (Think Denotation with a "d" for dictionary). In other words, it is the raw, unbiased meaning of the word. Connotation on the other hand, is the extra baggage we place on the meanings of words. It is the reason why we classify words into degrees of positive and negative. As society and language has evolved, certain words have been used in certain ways that cause different feeling to be associated with certain words.
For instance, the dictionary definition of a rose may just be something related to a red flower with thorns on the stem (I'm simplifying of course). However, based on how roses have been used in literature and how they have grown to become the "it" flower on Valentine's Day, the rose has also been associated with exquisite beauty (beyond the definition of an everyday flower) and rareness and love. The connotation then of "rose" is much more positive than what the denotation indicates. Of course, the connation could also be much more negative in other cases.