Cognates are words of different languages that are related, that is they have a common etymology.
Examples of cognates are English to pay and French payer. Another example is French venir and Latin venire (both meaning "to come"). These words are cognates since they originate in the same root (English borrowing "to pay" from Norman French, and French inheriting venir by the course of language evolution from Vulgar Latin).
False cognates are words that commonly thought to be related while they're really not. Thus, for example, many people think that the Latin verb habere and Germanic haben are cognates. However, judging by the way both languages inherit Indo-European roots, the real cognate of the Germanic haben is Latin capere, "to capture" (note however that Germanic haben and English to have are cognates, and so are Latin capere and English to capture).
It has been calculated that if one takes a word from a language, there's a 40% chance that one will find a word with roughly similar sound and meaning in another random, non-related language. Because of that, even finding several hundred similar-sounding words in a couple of languages is not enough to demonstrate that the languages are related to each other. Moreover, over the course of hundreds and thousands of years, words may change their sounding completely. Thus, for example, English five and Sanskrit pança are cognates, while English over and Hebrew a'var are not, and neither are English dog and Mbabaran dog.
Although perhaps not technically accurate, the term "false cognate" is sometimes used to refer to false friends, pairs of words in different languages that look like they might mean the same thing but don't. These words are famous for tripping up beginning language students. An example is the Spanish compromiso, which means "promise," not "compromise." Note, however, that though these have different meanings, they are actually cognates.
See also Historical-comparative linguistics.