At various times, I've done some genealogical research about my family, with some, but limited success. I recently gave it a try again, to great effect. The tool PhpGedView is a nice PHP based genealogy database manager, though it requires a few too many clicks to do most things. Further, RootsWeb WorldConnect is an outstanding searchable database of people's posted Gedcom files. (Gedcom is the standard format for genealogical data) All this looking was actually inspired by seeing the WikiTree project, which is an interesting idea, with a mediocre to poor implementation and a number of somewhat deep flaws. WorldConnect accomplishes the goal of large shared genealogy much more effectively, even if that's imperfect as well.
In any case, I've managed to trace back to the 16th century for parts of my family and back to the 14th century for parts of my wife's family. Very cool. The three big issues there seem to be with genealogy tools are that all the UIs are mediocre at best, GEDCOM merging tools are weak and annoying to use at best and the kinds of family graphs you can generate are surprisingly minimal. On the graphing issue, everything provides ancestry trees and descendent trees, but usually that's the end of that. PHPGedView has a nice "hourglass" graph which is ancestry and descendents of one individual glued together. What I wanted was a graph that included everyone. So, I wrote a ruby script to parse out GEDCOM files and generate href=http://www.graphviz.org/>dot input file, and used that to generate the graph. It works. In addition to the entirely illegible version at right, there is a large version of my family tree where I'm the red one. The squares are people and the black circles are marriages. The resultant graph is nice.
So, if your last name (or that of your ancestors) is Gray, Lounsbury, Mentzer, Robe, Wilhelm or Stafford, we might be traceably related. Of course, probably not.