How did Buddha's teachings about samsara differ from earlier Indian tradition? Even before the Buddha, the wheel of birth and death was a common teaching in India, with the six stages or realms. This is something that has passed down into Buddhism (even today). What did the Buddha add to this traditional teaching, and how does the Buddhist conception of samsara differ from this older teaching?
I’m not sure what you mean by six stages here.  Actually, it seems that the rebirth/samsara concept was not that old when Buddhism came on the scene.  Gananath Obeyesekere is an anthropologist who wrote a book about rebirth across a range of cultures.  He begins by trying to situate the Buddhist idea of ethical rebirth in the history of Indian religion:


  I will begin with Hinduism and the problem of origins.  The association between karma and rebirth is not at all clear in the earliest texts and discourses on Indic religions.  There are virtually no references to rebirth or to an ethical notion of karma in the Vedas or in the BrāhmaNas, the oldest texts belonging to the Hindu tradition.  The first significant references appear in an early Upanishad, the BRhadāraNyaka UpaniSad, probably composed sometime before the sixth century BCE, followed by the Chāndogya and the KauSītaki.  A hundred years or more later these theories appear in full bloom in the so-called heterodox religions – particularly in Buddhism and Jainism – that have karma and rebirth at the center of their escatological thinking.  Soon afterward these ideas surface in mainstream Hinduism itself and become an intrinsic part of the eschatological premises of virtually all Indic religions.


Karma in the Vedas and karma in Buddhism are different:


  The word karma, which etymologically means “action,” has the meaning of “ritual action” in Vedic (pre-Buddhist and pre-Upanishadic) thought, where it is neither fundamentally ethical nor related to rebirth.  By contrast, in Buddhism karma refers to intentional ethical action that determines the nature and place of rebirth, and this definition of karma has influenced the many Hinduisms that came after.


In The Wonder that was India, A. L. Basham writes about “transmigration” as a new development in Indic religion:


  As Āryan culture pressed further down the Ganges it absorbed new ideas about the after-life.  In the Rg Veda the fate of the dead seems to have been finally decided when they died – they went either to the “World of the Fathers” or to the “House of Clay”, where they remained indefinitely.


Basham cites the same Upanishad text as Obesekere as the first appearance of the rebirth doctrine, but in a “primitive” form.  In this text, he points out,


  this doctrine [...] is put forward as a rare and new one, and was not universally held at the time of the composition of the UpaniSad.  Even in the days of the Buddha, transmigration may not have been believed in by everyone, but it seems to have gained ground very rapidly in the 7th and 6th centuries BC.


It’s impossible for us to know if the rebirth concept came from some other tradition within India, since no texts have survived.  Anyway, it seems to have been “in the air” during the Buddha’s lifetime.  Probably the intellectual appeal of the concept, the justification it gives to ethical behavior, helped Buddhism spread and establish itself.  Also, the whole point of Obeyesekere’s book is that this idea is not unique to India – you also find it in Native American cultures, for instance.

Sources (bold text is my emphasis):

Gananath Obesekere, Imagining Karma:  Ethical Transformation in Amerindian, Buddhist and Greek Rebirth (U. of California Press, 2002), pp. 1-2.

A.L. Basham, The Wonder that was India, (Rupa 3rd ed., 1967), p. 242.