For Genealogy Enthusiasts:
Use software to store and organize information.
Start with what you know. Collect as much information from relatives as you can, then get it organized, preferably with some genealogy software package, before turning to the internet. When you're organized you'll be able to take advantage of what the internet offers.
Evaluate everything you find!
Don't fire off e-mail with general questions to historical societies, libraries, discussion lists, etc. Many organizations (academic libraries) will not do genealogical research, but will help you use or locate material that is unique to them.
Don't ignore print resources! Electronic resources are useful portals to information--but often you will still have to order microform, photocopies of records, etc. Many print resources will not appear online for many years. Don't wait!
Good Luck with Your Research!