There are a few very old Precambrian rocks in Maine, but the state's history basically begins with activity in the Iapetus Ocean, where the Atlantic lies today, during the Late Proterozoic Era. Plate-tectonic activity similar to what's occurring in southern Alaska today pushed microplates onto the Maine shore, deforming the region into mountain ranges and spawning volcanic activity. This happened in three major pulses or orogenies during Cambrian to Devonian times. The two belts of brown and salmon, one at the extreme tip and the other starting at the northwest corner, represent rocks of the Penobscottian orogeny. Nearly all the rest represents the combined Taconic and Acadian orogenies. At the same time as these mountain-building episodes, bodies of granite and similar plutonic rocks rose from below, shown as light-colored blobs with random patterns.
The Acadian orogeny, in Devonian time, marks the closing of the Iapetus Ocean as Europe/Africa collided with North America. The whole eastern American seaboard must have resembled today's Himalaya. Surface sediments from the Acadian event occur as the great fossil-bearing shales and limestones of upstate New York to the west. The 350 million years since then have mainly been a time of erosion.
Around 250 million years ago, the Atlantic Ocean opened up. Stretch marks from that event occur in Connecticut and New Jersey to the southwest. In Maine only more plutons remain from that time.
As the land of Maine eroded, the rocks beneath continued to rise in response. So today the bedrock of Maine represents conditions at great depths, up to 15 kilometers, and the state is noteworthy among collectors for its high-grade metamorphic minerals.
More details of Maine's geologic history can be found in this overview page by the Maine Geological Survey.