Start your Maine search with these suggested resources:
The Brick Store Museum in Kennebunk maintains genealogical file folders on families historically associated with the region.
Maine Genealogy and History, part of USGENWEB, contains innumerable resources.
Maine State Historical Society is comprised of the Wadsworth–Longfellow House and Longfellow Garden, the Maine Historical Society Museum and Store, the MHS Research Library and the Maine Memory Network. A growing museum, incomparable library and statewide educational resource, was founded in 1822 and is the third oldest state historical society in the United States.
On September 28, 2011, a new law regulating access to vital records took effect in Maine. Original vital records in Maine may be accessed through three venues, described in this link.
National and International in scope
National Archives- contain census records from 1790 - 1920; military records Revolutionary War to WW1; military pension records; passport applications back to 1795; ship passenger lists; naturalization; more
Ancestry.com Includes Social Security Death Index (to find death records by date of death or SSN) and many other databases.
Family Search has a weath of information gathered by the Church of the Latter-day Saints.
Cyndi's List links to 282,000+ links for family genealogy - everything from ship's passenger lists to prison rolls.
Roots Web, internet's oldest genealogy site, lets you see who is looking for the same surnames you are.
National Genealogical Society, a non-profit organization begun in 1903, is the premier national society for everyone from the beginner to the most advanced family historian.