First, there was nothing. Absolutely nothing.
Then,
In the beginning there was only Chaos. Then out of the void appeared Erebus, the unknowable place where death dwells, and Night. All else was empty, silent, endless, dark. Then, Love was born bringing along the beginning of order. From Love emerged Light, followed by Gaea, the earth.
http://www.greekmythology.com/Myths/The_Myths/The_Creation/the_creation.html
That's one version. Another explanation is
It all started when Chaos, Gaea (Earth) and Eros started sleeping with each other, leading to the Gods. So, in Greek mythology, the creation of the world starts with the creation of the different classes of Gods. In this instance, the term 'gods' refers to the characters that ruled the Earth (without necessarily possessing any divine attributes) until the 'real' Gods, the Olympians, came.
http://www.greekmythology.com/Myths/The_Myths/The_Creation_II/the_creation_ii.html
These are based in Hesiod's Theogony. I was able to find an actual quote from it:
Declare to me from the beginning, you Mousai who dwell in the house of Olympos, and tell me which of them first came to be.
In truth at first Khaos (Air) came to be, but next wide-bosomed Gaia (Earth), the ever-sure foundation of all the deathless ones who hold the peaks of snowy Olympos, and dim Tartaros (the Pit) in the depth of the wide-pathed Earth, and Eros (Love), fairest among the deathless gods, who unnerves the limbs and overcomes the mind and wise counsels of all gods and all men within them. From Khaos (Air) came forth Erebos (Darkness) and black Nyx (Night); but of Nyx (Night) were born Aither (Light) and Hemera (Day), whom she conceived and bore from union in love with Erebos. And Gaia (Earth) first bore starry Ouranos (Heaven), equal to herself, to cover her on every side, and to be an ever-sure abiding-place for the blessed gods. And she brought forth long Ourea (Mountains), graceful haunts of the goddess Nymphai who dwell amongst the glens of the hills. She bore also the fruitless deep with his raging swell, Pontos (Sea), without sweet union of love.
But afterwards he [Gaia, Earth] lay with Ouranos (Heaven) and bare deep-swirling Okeanos, Koios and Krios and Hyperion and Iapetos, Theia and Rhea, Themis and Mnemosyne and gold-crowned Phoibe and lovely Tethys. After them was born Kronos the wily.
-- Hesiod, Theogony 115
Aristophanes had a slightly different version:
At the beginning there was only Khaos (Air), Nyx (Night), dark Erebos (Darkness), and deep Tartaros (Hell's Pit). Ge (Earth), Aer (Air) and Ouranos (Heaven) had no existence. Firstly, black-winged Nyx (Night) laid a germless egg in the bosom of the infinite deeps of Erebos (Darkness), and from this, after the revolution of long ages, sprang the graceful Eros (Love) with his glittering golden wings, swift as the whirlwinds of the tempest. He mated in deep Tartaros (Hell-Pit) with dark Khaos (Air), winged like himself, and thus hatched forth our race [the birds], which was the first to see the light. That of the Immortals did not exist until Eros had brought together all the ingredients of the world, and from their marriage Ouranos (Heaven), Okeanos (Ocean), Ge (Earth) and the imperishable race of blessed gods (Theoi) sprang into being.
-- Aristophanes, Birds 685
In both cases, Gaea is understood to be a personification of the Earth; the same goes for Chaos, Erebus/Erebos, Eros, and many of the others.
For information on just how Gaea begat her children, see How were the first children of Gaia conceived?.