Write Down What You Know
The best place to start is by printing and filling out a pedigree chart, also known as an ancestral chart. This resource will prove invaluable, both in beginning your research, and as you continue to gain more knowledge of your ancestors. It is also going to help you keep what you learn organized.
You can find pedigree and ancestral charts for free at numerous websites, but in searching for one to recommend, I couldn't find a chart as good as the pedigree form I had been given at my local genealogy library upon my first visit. Unfortunately, neither could I find that exact form online, so I created this one (save and print as needed).
Using a Pedigree / Ancestor Chart
A pedigree is basically a spreadsheet showing parental lineage over a number of generations, which may be continued on a fresh page to reflect unlimited generations. On the first sheet of your pedigree, you will enter your name in field number 1 on the left hand side of the chart.
Note: I recommend printing out blank charts and filling them out in pencil, as it makes correcting mistakes and adding additional information, such as middle names and cities (when you at first only knew the county), much easier.
Your parents will be recorded in fields 2 and 3. Customarily, the father of the person in field 1 is number 2 on the chart, and the mother is number 3. Following this pattern, all male entries on the chart will have even numbers, and all female entries will have odd numbers (obviously the person in field 1 will be an exception to this if they are male).
Some pedigree charts don't number the individual fields, but those that do will make your research much easier as you add more generations, as well as different types of genealogy forms to your collection.
Continue to fill out the generation chart in this fashion, adding your paternal grandparents to your father's branch of the line (fields 4 and 5), and your maternal grandparents to your mother's branch (fields 6 and 7). Fill out as much information as you think you know about each generation of your family.
If you already have names for more generations than will fit on the first page of the pedigree chart, go ahead and number this first chart as 1 in the "Chart Number ____" field. You may also notice that there are tiny little blank lines next to the name fields of the last generation on the chart, which may or may not be labeled to show their exact usage. In these blanks you will indicate which chart number each of these relatives' lineage is continued on.
To avoid future confusion, go ahead and number these blank fields from top to bottom, starting with 2 (since this is chart 1). If you have a five generation pedigree, the great great grandfather along your father's paternal branch (person number 16) will be continued on chart 2. Your maternal great-great grandmother in field number 31 will be continued on chart 17. For a four generation pedigree, the ancestor in field 8 will be continued on chart 2, and person number15 will be continued on chart 9.
You can go ahead and print out and number the charts you will need to continue each line of your family tree (what I did), or you can print them out as needed. Just be sure that you label each subsequent chart with the number corresponding the chart number you assigned to each member of the last generation appearing on chart 1.
There is also an area on the chart that will say something like, "Person Number 1 on this chart is the same as Person Number _____ on chart _____". So if you are continuing chart number 2 from person number 16 on chart 1, this person will be "the same as Person Number 16 on Chart Number 1".
Write Down What Others Know
Once you have filled in all the information you "think" you know, a good place to turn next is to older family members who may be able to offer more information. But again, I would advise that you fill out your pedigree in pencil. This is not your "official" genealogy, this is your starting information, all of which will have to be verified. Family memories are fallible, and just give you a lead to go on.
Example: My father told me his paternal grandfather was born in Holland in 1888. He had the year right, but after a very frustrating search of immigration records, I eventually came across his WWI draft registration card, which stated he had been born in Gonzales County, Texas.
So I thought maybe HIS father had been born in Holland, and the story got skewed. Nope, his father was born in Gonzales County, too. Maybe it was another generation back? Nope, Alabama. I don't have any idea how "Holland" got into the oral family history, but I haven't found any evidence to suggest that it's true. Moral: use a pencil.
Next Step, Easy to Find Documentation.