Stories travelled in Biblical days too - they were a bit slower than the internet, but people have always loved to sit around listening to tales of wondrous happenings.
A traveller from far away, stopping for the night in a wayside dwelling, would "pay" for his meal and bed by recounting the strange things he had encountered. Some of those encounters were true, but embellished for the ocasion, some were ones he had heard other travellers tell - which had themselves been edited and improved in the repeating.
A good story would spread faster than a boring one (just as on the internet) so no wonder legends in many areas have great similarity.
