The first true pyramid was build by the architect Imhotep (a man who wore many hats, including that of physician) under the patronage of King Djoser, the first ruler of the Third Dynasty of Egypt. This is the famous Step Pyramid, so called because of the step-like appearance of the sides. Later pyramids would be given smoother sides. The Step Pyramid was built ca. 2650 BCE at Saqqara.

His immediate predecessor, Khasekhemwy of the Second Dynasty, had a tomb built for him in Abydos. Djoser's tomb in many ways was a refinement of Khasekhemwy's structure: Mastabas, or flat mounds would be placed over the Second Dynasty tombs.

The underground burial complex of Djoser's was similar to that of Khasekhemwy's. Both supported great weight above, both had niched enclosure walls. However, Khasekhemwy's enclosure wall was further from the tomb than was Djoser's. It is speculated by many archaeologists that Djoser's originally started as a mastaba, with a flat mound. However, more flat mounds, each smaller than the one below, were added to the structure. The archaeologist Guenter Dreyer adds evidence relating to the enclosure walls to this theory -- he speculates that the closeness of the enclosure wall hid the mastaba mound from view, and so to announce Djoser's tomb more prominently, a series of flat mounds were built atop the original mastaba, elevating the final structure to a pyramid.

Casting our gaze back further into time, we note that the earliest tombs of the ancient Egyptians largely did not survive the elements and the millennia between them and us. Evidence leads us to believe that up to the end of the fourth millennium BCE tombs were merely pits, perhaps lined with wood or some other perishable matting. Any structures that may have been built atop such pits is the province of pure speculation.

Around 3200 BCE, the archaeological record presents brick-lined underground chambers with perhaps one or two side chambers. These graves had wood beam roofing. These would be the final resting places of the important figures of that time. Wood coffins, and grave goods, have been found in these. These grave goods often were small models which depicted houses, and might be made of ivory or of wood, both rare and valuable materials.

At Abydos, beginning about 3100 BCE, the tombs of rulers of Dynasty 0 and Dynasty 1 have been found. These are broad brick-lined pits with rectangular chambers. Wooden beams and large stone blocks were also used in their construction. Steps led down into the tombs. Stelae with hieroglyphs would be placed facing the direction of the rising sun. Cultic centers (the niched enclosure walls) would be constructed relatively nearby. At the south east corner of these enclosures, there would be a gate. Most of the cultic buildings have disintegrated over the ages.

Graves were also constructed at Saqqara during a portion of the Abydos stage: at first the Saqqara interments were those of the nobility of nearby Memphis, although by the Third Dynasty, the pharaohs began entombing themselves there as well.

References:

1. Dietrich Wildung, Egypt from Prehistory to the Romans, 2001, Taschen. ISBN 3-8228-1221-8.
2. a since-expired news item from Yahoo News, written by Jonathan Wright.