Gramps: Open-Source Genealogical Research Software
gramps-project.org
gramps-project.org
Look into local archives, church records. Then go on-line at FamilySearch.org, Ancestry.com, MyHeritage.com, Cyndislist.com. Where you go will depend on the country of origin of your ancestors.
Keep a careful record of your sources. You might have to revisit them when you come across contradictory information.
There are many free programs to record your information: Legacy, RootsMagic, Ancestral Quest.
Who are the people using this? Why they need so many options?
For example this classic question [1] contains an example:
"The problem is that he has two children with his own daughter, and, as a result, he can't use my software because of errors."
In my family past I've seen some strange things too, but nothing quite on that order.
[1] - http://stackoverflow.com/questions/6163683/cycles-in-family-...
(Well obviously there is a mother in the biological sense, but it might be that the data isn't available. Instead in tracking a "family" tree you'd have two fathers.)