Finding anything is tough... I did find an overview of pre-Roman occupation at http://72.1911encyclopedia.org/C/CY/CYPRUS.htm
http://www.stonepages.com also has a couple of references to found tombs etc. Doesn't seem to be much there though...
They had a pretty active Bronze Age society going on there and traded copper ingots, daggers and pottery all over the med. Can't find any references to any megaliths on the island.