Take note that the dance and a song are two parts of a whole.
Most familiar with the the meme would know that the title is Swedish for "Caramel Dance" and comes from the first track of the album Supergott released in November 2001, by the Swedish band "Caramell."
What's important about this is not the music but the animated dance that make up this meme. The meme is said to have appeared during the second half of 2006.
While its exact date of inception is uncertain, for a fact, this means started as a fifteen frame Flash animation loop showing Mai and Mii, who are characters of the Japanese (adult) visual novel Popotan, doing some sort of swinging hip dance while holding their hands over their heads imitating some sort of animal ears. The music played in the background was a sped up version of the song aforementioned song sung by singers Malin and Katia from the aforementioned band. There were other remixed versions that showed up almost in parallel, but that's not the most important part about this meme or its dance.
You see this popular dance clip originated from gif loops of the game's OP:
https://youtu.be/--Yr5q6tU9A?t=102
The game itself was released in 2002, with an anime following it in 2003. So why did it take so long for the meme we know today to appear?
It's possible that the anime, being anime, was more available to the public than its adult visual novel counterpart. For obvious reason such as content and availability, since fast broadband and Youtube (it appeared early 2005) were as readily available and prominent as it is today.
There's evidence to suggest that the a similar loop from the anime brought attention to the game. This particular loop was created based off a loop of the character Mii from the OP of the anime:
https://youtu.be/tboQg1xj010?t=62
This particular loop was probably made sometime around when the anime aired in the later half of 2003: http://dagobah.biz/flash/miidance.swf
Clearly the game's dance sequence would be considered cuter by most fans. Before Caramelldansen was even a thing, there were many other remixes being called different things with different songs from different bands playing, from Aerosmith and Run DMC's "Walk the Way" to "Dare" by the Gorillaz, most of them done in Flash. Subsequent spin-offs were created based on original characters and popular characters alike. But where and when did the meme in question start its popularity?
Apparently a guy from Sweden by the name of Sven, created the flash loop and posted it on his personal website: http://md5.se/h/032/
From there it made itself across the internet in the later half of 2006. Originally many large communities such as Hongfire and 4chan "Popotan Dance" or "Popotan Dansen," but as after 2008 it became more popularly known in its country of origin, Japan, as the "uma uma dance."
However it's believed that it wasn't until early 2008 that the meme truly popularized, with the help of versions and remixes shared via video sharing communities such as Youtube and Nico Nico Douga where its popularity truly peaked.