The Heruls in Scandinavia are not indentified in the works of the geographers or historians written before 550 AD, when Jordanes in The origin and deeds of the Goths tells of them in association with the origin of the Goths.
They are known from historical sources firstly as a tribe accompanying the Goths around the Black Sea, participating in attacks on the Greek territories of the Roman empire in the latter part of the 3rd century, from 236 AD until 269 when the Heruliis were defeated by Gallienus, and then returned to the southbank of the Donau (Danube). The Byzantine Procopius (secretary of the east-roman emperor) described the Heruls migrating from Southeastern Europe to Scandinavia around 510 AD, setting off for the land of 'Thule'. Later in the sixth century, the remaining tribe of the Heruls at the Balkan lost their king, and sent for a new king with the right ancestory from their northern tribe settlement - wherever this was.
Apparently they worshipped a God named Gaut, mostly assumed to be another name for Wodan, the German version of Odin. Accidentally, Gaut happens to be one of the names used by Odin, and is also the name of his ancestor according to Snorri Sturluson in his Heimskringla.
A special group of Heruls, the Western Heruls, were for the first time mentioned by the Romans in 286 AD. They seem to have settled at the coast of Frisia (Netherlands) as early as in the third century when the Frisians temporarily left the coastal area due to a rising of the sea level. These Heruls plundered the coasts of France and Spain as pirates, but it is not known if they arrived from Scandinavia, from Poland or from the Black Sea-area.
See http://www.geocities.com/troels_brandt/heruleng.html for thorough discussions on them.