First cite for this in OED is this:
1537 LD. CROMWELL in Ellis Orig. Lett. Ser. I. II. 101 The Kings Maiestie, about a twelfmoneth past, gave a pardonne to a company of lewde personnes within this realme calling themselves Gipcyans, for a most shamfull and detestable murder.
The Straight Dope says:
Anthropology professor Anne Sutherland in Gypsies: The Hidden Americans (1975) says the word Gypsy derives from the time when the Romani entered Western Europe and “represented themselves as Egyptians,” the name subsequently evolving into Gypsies.
Do any other European languages use a form of the word Egyptian (or its equivalent) for the Romani?