[Rumil]

Good point ecthelion,

I remember that they were noted as being evacuated from Numenor on Elendil's little fleet.

So either they were brought to the Numenoreans out of Tol Eressea, during the times that the elves still had good relations with the Kings, or they had been given to the Three Tribes in Beleriand, or they were a gift from the remaining elves (eg Gil Galad) during the Second Age.