The origin of cultural evolution is an area which has been studied extensively in academia. For some reason, many academics in the field seem to have specialized in the pre-history of cultural evolution - an area where we have a paucity of data and which it is difficult to explore experimentally. Why this happened is another story, but it did happen - and as a result we know more than we otherwise would about the origin of cultural evolution. In particular the work of Boyd and Richerson - as reported in their 2005 books - significantly illuminates this subject area.
They speculate that the glacial climate of the current ice age provided a challenging, spatio-temporally varying environment for our ancestors - and a variable environment increases the benefits provided by rapid cultural adaptations. They also suggest that the mild climate in the modern inter-glacial period led directly to the modern flourishing of humanity.
The doctrine of common descent suggests that all living things share a common ancestor. If taken literally, this means that the first memes came from evolving ideas within minds - and these ultimately arose from DNA genes. The initial dependence of cultural evolution on DNA-based evolution suggests that cultural evolution doesn't violate the common descent doctrine.
However the origin stories of individual memes can certainly involve external influences that are neither genes nor memes. A classic example of this is "the face on mars" (see right). While elements of this meme arose within human brains and involved cultural artifacts - such as spaceships and telescopes - it is hard to deny that an important part of the meme originated on Mars.
Ultimately, the origins of cultural evolution should be traced back beyond our common ancestor with chimpanzees (since these also carry a significant cultural inheritance with them).