There are also database programs available to store your information.  Many of them have features such as photo albums, family tree charts and reports, "to-do lists", research journals, citing sources, and much more.  Here is a web page that list programs available:

http://www.lkessler.com/gplinks.shtml

Begin with yourself and work backward.  Get as much information about yourself and your siblings, if you have any.  Get the date and location of major events in their lives (i.e. births, marriages, and deaths).  Do the same with your parents and any siblings they have.  Continue backward with each previous generation until you reach the immigrant ancestor(s).

There are many great sites to help you get started:

Family Tree Maker's Genealogy How-To Guide
How Do I Begin? -- from the LDS; contains listings of holdings and locations
Getting Started-- from the National Genealogical Society
Your Great Ancestral Hunt -- extensive coverage of researching the family tree

These are several sources of records available in the United States.

BIRTH RECORDS.  The birth record will often supply the names of the parents and the city of birth.  It may also have the place of birth of the parents.  If your state offers a choice between the short form and the long form, be sure to request the long form.  The short form often includes only the name at birth and the date of birth.  Before the advent of Social Security, many births were not recorded with any civil office.  In 1937, when Social Security was established, many delayed birth records were filed.  So, if you've searched fruitlessly for a birth record for your ancestor, try searching the years when he would have been old enough to work or the year he would have retired.  Delayed birth records are filed in the year they are submitted, not in the actual year of birth.  Note: If a birth record cannot be located for your ancestor, don't forget to request records for any unnamed child born with his/her surname.  Ocassionally, a first name wasn't provided on the birth record, particularly prior to centralization of records at the state level.

Vital Records Information for United States -- how to obtain birth, marriage, and death cerificates in the U.S.

MARRIAGE RECORDS.  Marriage records are held by the county in which they took place in most states.  Information included depends upon the time frame and location.  Some records were very detailed and included the birth date of each party, the location of birth, and residence at the time of the application being filed.  Others provide only the "bare essentials," which were name and age.

DEATH RECORDS.  The information found on death records was supplied by the person reporting the birth or death.  Keep in mind that this person may have unknowingly given incorrect information.  Not everyone's memory is 100% accurate, especially immediately after the death of a loved one!  By obtaining the birth record, you will confirm the date on the death record.  Also, in more recent years, the place of interment is usually provided on those records, along with the name of the funeral home or undertaker.

CHURCH RECORDS.  Records of baptisms, marriages, and deaths from the church can often supplement information found on the civil records.  Many churches recorded the birthplace of the parents on baptismal records and on marriage records.  This is particularly helpful when researching births and deaths prior to records becoming centralized in each state.

CEMETERY RECORDS.  Write to the cemetery where your ancestor is buried, and be sure to request the names and info for all persons buried in the plot.  Otherwise, many cemeteries give you only the names you ask for!  The information on cemetery records can be useful in providing the date of death and burial and can provide you with death/burial dates for others in the plot whose info you don't have.  Beware: some cemeteries charge fees for this information, and some require the date of death for the person you are looking for.

Cemetery Records on the Internet -- online records for the U.S., Canada, United Kingdom, Australia, and other countries
The USGenWeb Tombstone Transcription Project -- online source of transcribed tombstone incxriptions from the USGenWeb project.

FUNERAL HOME RECORDS.  These records can be very helpful.  Of course, the death and burial dates will be provided.  Other information may include place of death, place of burial, place of residence, certifying physician, cause of death, date of birth, place of birth, and parents' names.

Internet Directory of US and Canadian Funeral Homes -- if the funeral home you are searching for does not have a web page, the name, address, and telephone number can still be found here

CENSUS RECORDS.  The U.S. Census records are available for the years 1790, 1800, 1810, 1820, 1830, 1840, 1850, 1860, 1870, 1880, 1900, 1910, and 1920.  The earlier the year you are searching for, the less information you will receive.  Until about 1850, only the heads of households were named.  At the very least, you will obtain an age and the place of birth (state or foreign country).  However, the information on these records cannot be accepted as 100 percent factual unless confirmed by another source.  Ocassionally, information was provided by a neighbor when the residents were not at home when the census taker visited.  For more information on census records, see NARA.

PASSENGER LISTS.  Each port of immigration was required to keep records from the early 1800s to the present.  Many of these records are on microfilm at various libraries, LDS Family History Centers, and the National Archives and Records Administration (NARA).  You will find the name of the port from where the ship sailed, the name and age of your ancestor, and any persons accompanying them.  Port records vary in content depending upon the time frame.  Information may also contain last place of residence, place of birth, name of nearest living relative, intended destination once in the United States, among other bits of information.

HINT: Don't forget to look in the book series Germans to America for your ancestors.  For those of you who are not familiar with this series of books, it is a compilation of German passengers arriving at the port of New York from the mid to late 1800s. It does not list only those passengers with German surnames, but any German citizen.  Those living in the Prussian partition of Poland were considered German.  The series is far from complete, but it is a valuable research tool.

See our Immigration and Naturalization page for more information and links to online resources.

NATURALIZATION RECORDS.  In 1906, the U.S. requirements for the naturalization process underwent a vast change.  A wealth of information became required on the records: full name, date and town of birth (not just the name of the country!); spouse's full name, date and place of birth; date and place of marriage; last place of residence in the foreign country (again, the name of the town!); the names and dates of birth of children; port of emigration, name of ship and arrival date; and the date of naturalization of spouse, if naturalized.  Don't overlook this valuable source of information!  The majority of U.S. naturalization records have been microfilmed.  Knowing the date of naturalization is not required if the records are indexed.  However, you must know the location of naturalization!

See our Immigration and Naturalization page for more information on American, Canadian, Australian, and New Zealand naturalizations and links to online resources.

MILITARY RECORDS.  These records should supply the birth date, birthplace, and service record.  Parents' names may be included, along with other information.

Reseaching in Canada

Cemetery Records on the Internet -- online records for the U.S., Canada, United Kingdom, Australia, and other countries
Internet Directory of US and Canadian Funeral Homes -- if the funeral home you are searching for does not have a web page, the name, address, and telephone number can still be found here
Using Canadian Records to Trace Your British and European Ancestors in Western Canada -- discusses immigration and naturalization records
National Archives of Canada -- click on the language of your choice and then choose SERVICES TO THE PUBLIC
inGeneas Database -- contains Canadian passenger and immigration records from the 18th, 19th and early 20th centuries; well-worth exploring

Researching in Australia and New Zealand

Special thanks go to Tom Wodzinski for the following information!

The National Archives of Australia has an excellent web site which provides a comprehensive description of their holdings, as well as online access to their electronic database and online ordering facilities.  A 330-page guide to the archives for those conducting genealogical reasearch in Australia -- "Finding Families - The Guide to the National Archives of Australia for Genealogists" -- is an invaluable research aid and considered to be a "must have" publication.

Naturalisation Records in Australia
The National Archives of Australia possesses a comprehensive index of surnames for all naturalisations after 1903.  Naturalisations prior to this date were held by the individual states, and these records are located in the State Offices of the National Archives.  The index of surnames for naturalisations after 1903 is especially valuable, since the majority of Poles immigrated in the 20th century.

Immigration Post WWII
In addition to naturalisation records, the National Archives possesses readilly accessible material on post World War II displaced persons who were accepted in Australia as part of the International Refugee Organisations resettlement program in the late 1940s and early 1950s.  The amount of resource material available is reported to be quite large.

Links

The National Archives of Australia
Polish Genealogical Society of New Zealand -- from FEEFHS (Federation of East European Family History Societies)
AUSNZ Passenger Lists -- on-line sources
Polish Organisations in Australia by state
Cemetery Records on the Internet -- online records for the U.S., Canada, United Kingdom, Australia, and other countries

What is needed to research in Poland?

Before you send to Poland for records, check your local Latter Day Saints' Family History Center (FHC).  Many records from Poland have been microfilmed by the LDS Church.  If those for the area in which you are seeking are among the microfilmed records, it will save you a great deal of money to simply order the roll from your local FHC.  Sending to Poland for records can be quite expensive and can take months (even as long as a year!) to receive a response.

You must have enough information to begin searching in Poland.  First, you will need the location of the event (birth, marriage, death) for your ancestor.  Keep in mind that there may be more than one town with the same name!  It is not uncommon to find two or more towns, located in different provinces, possessing the same name.  You may need to send to some (or all) of the locations to find the correct record.  See Frequently Asked Questions for town locators.

You will also need the date of the event (birth, marriage, death).  Without the date, it may prove impossible to locate the record you seek.  There may be more than one child with the same name born in your ancestor's town within a certain year or month.  However, if you have the parents' names, you may be able to determine the correct record without the exact date.

See Obtaining Polish Records for where to send for records in Poland.