Until Dawn emailed us "... you should put the difference between compliment and complement - a great one!", we hadn't even thought about this!
Compliment can be a noun or a verb and is all about being nice to people.
e.g. "The judge paid Andrew the compliment of singling out the excellent quality of his blackberry pie."
As a verb, compliment is usually used like this:
"Vicky complimented her boyfriend on his excellent choice of clothes."
Complement means "to go well with" or, by having something, it "makes something even better than before".
e.g. "The glass of port was a fine complement to the selection of cheeses."
This word is regularly used in describing the outfit that people are wearing.
e.g. "Gareth's snakeskin belt complemented the lumberjack shirt he had on."