How to Start
Links to 11 great sites
Grandfathers in Queries
Beginning Internet Skills
Off the web
People after 1900
The LDS 1880
Googling your Ancestors
Main Genealogy Page
Essays on Genealogy
Most beginning genealogy sites tell you to start with what you know and work backwards. They will mention birth certificates, marriage licenses, death certificates, obituaries, funeral home records, cemetery records. Good advice, but the paper trail can wait.
The first thing you should do is contact your oldest living relative. Apologize for not writing and calling more frequently. Tell him or her she or he is an interesting person. Gradually steer the conversation to dead ancestors. Record the name, birthplace and name, death place and name of everyone the OLR can remember. Try for legal names and maiden names; "Mrs. Smith" and "Slim Jones" won't appear on census records or birth certificates. More important, ask what they were like; what they did for fun, what they did for work, milestones in their life. Vital records won't tell you great-grandfather George struggled through the Great Depression on $60 a month, or that he memorized sonnets to woo Great-grandmother Irene.
I have a Biography Outline, if you are interested. It is a series of questions you can ask your OLR - or yourself, for that matter. Some people have a hard time thinking of anything to write, and some of us ramble along for hours at the slightest provocation. The Outline is for the first kind of people.
Turning now to the tools you should have, get a computer program. Trying to build a family tree without one is like trying to write a novel without a word processor; possible, but tedious. The Mormons will let you download their PAF program for free. I use Roots Magic. A very popular one is Family Tree Maker. It comes with CD's of family trees. It starts at $59 and goes up depending on how many CD's you buy. The family trees vary in quality, and there is no guarantee you will find an ancestor on one.
Once you interview your OLR, start with what you know and work backwards. Birth certificates, marriage licenses, death certificates, obituaries, funeral home records and cemetery records will all help. Marrige write-ups in the social columns of newspapers will help; besides telling you the bride wore white ogandy, they will mention the best man was the groom's brother Earl, and the Matron of Honor was the bride's aunt Pearl.
The Web has millions of pages devoted to genealogy. There are whole sites devoted to getting started. One of the best, which is much more comprehensive than mine, is the RootsWeb Guide To Tracing Family Trees. They have 30 lessons, written by professionals.