Something I've found success with is going back as far as I can on a particular line and when I get stuck, I go to the other end and try to find immigrants or early settlers of the name I'm looking for. Sometimes I am able to meet in the middle by working forward. This is how I found my Scottish clan. My g-grandmother was a Hester. I got back a couple of generations more but hit a dead end. Then, in researching for my SAR membership I found several Hester/Frazier marriages in the DAR books. I traced them forward and was eventually able to connect my line to one of them. A lot of it also was just a process of elimination.

I've also found people often race ahead and make assumptions that so-and-so was such-and-such's son becuase you've got a name or two in the same area but then you start checking dates and you realize so-and-so must've been one virile son-of-a-gun to have fathered a child at age 3!

And, as others have said here; document, document, document.