Edit: Wait a minute, though matka and ojciec are the words for mother and father in Polish, little kids might say more mama and tata. I might have answered my own question here, but I too noticed some in the linked web page did not sound particularly similar to me.
For example, take German and Latin: I assert the words Vater and pater (both 'father') are cognate, but to do so, I need to examine a whole set of corresponding words in both languages, so I take the sets {Vater, Fisch, Fuß} and {pater, piscis, pes}. From these, I can see clear correspondences (e.g. a German f sound always corresponds to a Latin p sound[1], the Latin sc seems to correspond to the German sch) and some things that are unchanged.
Next, I come up with a set of roots like {pater, piš, pes} and a set of rules to apply like {p → f in German, š → sc in Latin, š → sch in German}, and I can state with some confidence that these words descend from a common root.
In practice, you'd do this with way* more than three words—preferably you'd use most of the language—and there is some wiggle room for related meanings or exceptional changes, e.g. the German word alt and English word old seem unrelated to the Latin word senere 'to be old', because they actually stem from words for 'to grow up', and are therefore cognate to the Latin altus 'high, tall'. Additionally, some rules are more plausible than others based on research and phonological considerations, so the change of s → h is well-attested in actual languages and is consistent with similarities between the two sounds, while the change of r → b is highly unlikely.
And while there is some room for error, there is a limit e.g. one might argue that English and Japanese are cognate because in Japanese, 'to eat' is taberu and 'to see' is miru, and in English we eat off a table and see in a mirror. This doesn't get borne out with more thorough phonological rules and doesn't seem to reflect regular semantic processes, either.
tl;dr: Two words are cognate if they come from a common root; without direct knowledge of the parent language (e.g. Latin for Italian and French), we postulate one and show that regular processes can derive the child languages' vocabulary.
[1]: If you don't speak German, know that the German v is pronounced like an f.
Take a look at:
http://starling.rinet.ru/cgi-bin/response.cgi?root=%2Fusr%2F...
Google translate does an ok job of the Russian if it ends up looking too confusing.
But whatever the details - the reason ojciec and vater don't sound related to you is because they aren't, they don't share a root.
This does pop up even for very basic words in related languages with well-established common origins. Water, Wasser and woda sound related - the Latin aqua, not so much. It's not hard to imagine a relationship between fire, Feuer and, say, pyros (like in pyromaniac) but not so much with ogień. Then again, ogień, 'ignite' and 'agni yoga'. The reason for these seems to be that PIE had two different roots each for fire and water, respectively.
Sometimes the common root lives on in fairly different words - Nebel, nebula, nebo share a root. More unexpectedly, so do guest and hostile. Or German Gift and English gift.
And then you have the real winners like 'kobieta' the origin of which is essentially an unsolved mystery.