Here's a mystery: matrilineal societies don't usually give more power to females, so why do they bother to determine descent through the mother? What would cause a culture be matrilineal?
There isn't one single answer for all societies, but in many cases the answer seems to be simply that the babies come from the mother's body. You may not be sure who the father is, but you certainly know the mother. Of course, in most societies the father is quite invested in claiming his children as his own, and not some random bastard, so this is as much a spiritual recognition of the connection than a social recognition of the uncertainty of paternity. It is, however, important to note that matrilineal descent is not simply a matter of who carries the family name; it is often paired with avunculocal residence, in which the male children, upon reaching adolescence, will move into their uncle's house -- as he is the closest male adult family member of the family line.