Here's the difference:
Complement: Use this when your intended meaning is to suggest that something completes or enhances another thing.
Example: Brad wore a blue shirt on Saturday that complemented his blue eyes. --This means that his blue eyes were enhanced by his wearing the blue shirt.
Compliment: Use this when you want to give praise or flatter something or someone.
Example: I told Brad he looked really good in that blue shirt. I gave him a compliment.
An easy way to remember: Complement = Complete or Enhance.
Be careful though: Complimentary does not only mean to give praise. It also means free, as in a complimentary breakfast served at a hotel.