Starting with the Facts
Start with what you know about yourself and those relatives that you knew. Always work from the known to the unknown. Enter all the dates and facts that you can find. Speak with living relatives and gather any family records that you can such as diaries, bibles, photographs, wills, vital statistics (such as birth, christening, baptism and obituary notices) and letters. Get to know your history as it may give clues as to where ancestors migrated. You may find other tidbits as well including family histories. For some this will be a small amount of data, for others this may keep them busy for quite some time. In either case, add all this info to your data, paper of electronic.
Consider the following when interviewing:
Note: When it is an option, the order of preference for copying old documents is: a digital camera (flash disabled), a scanner and then a digital camera using the flash and then a photocopier. Please note that a photocopier can expose documents to too much light which will cause premature aging. If using a digital camera, disable the flash.
Add successive generations to your family group data. Note: do not skip generations; this could be disastrous if errors are later found. When you have completed this initial search and data accumulation, begin to consider and focus on what your goals may be. You may wish to stop here at what you have obtained and be satisfied not to go further. You may wish to continue and if so, you should create a plan and set some goals.
Keep track of your searches and follow a plan. This will help when you wish to revisit them or to remind you that a particular source has been searched and to what extent that searches have been completed. Obtain as many records as possible with copies of the records. Photocopy, scan or transcribe everything that you find that may be of value in your research. Be thorough, prioritize yoursources, search all them that you found and keep track of them in your planner
Find others and collaborate on common ancestral research. Cousins may have already done some of the legwork for you and are willing to share. Do not take all that they have for granted though, check their sources and verify them.
Take advantage of free Genealogical Research advice. Yes, I said free, for many institutions such as libraries, archives and many others will help you in your quest by just asking the staff. They are professional in their field, and have a great deal of experience that you can tap into and best of all, they do not charge for their services. Some institutions will do limited research for free or for a nominal charge and possibly through the mails if you pay the postage.