The core of the Kedushah (in every amidah) consists of the two verses from Isaiah 6:3 and Ezekiel 3:12. The earliest source that mentions these verses is Tosefta Berachos 1:11. The introductory passage, nekadesh (in minhag ashkenaz) or naaritzach (in many other minhagim; possibly based on Isaiah 29:23), and the connecting phrases "le-umasam", etc.), were originally said only by the reader. The extensions of these passages on Shabbos are mentioned
by the Geonim; apparently the Ashkenazic minhag originated in Eretz Yisroel, and the Sephardic minhag in Bavel. For more details, see the articles on Kedushah in the Encyclopedia Judaica and the Encyclopedia of Jewish Prayer.
Ask a follow-up question