I had always taken gazebo to be, in the OED’s words, “a humorous formation on GAZE v., imitating Lat. futures like videbo ‘I shall see’ (cf. LAVABO),” but the OED goes on to say “but the early quots. suggest that it may possibly be a corruption of some oriental word,” and William Sayers, in “Eastern Prospects: Belvederes, Kiosks, Gazebos,” Neophilologus 87 (2003): 299-305, tries to pin down that “oriental” origin. As the abstract says:
An etymology for gazebo is sought in Hispano-Arabic and a likely candidate meaning ‘mirador, viewing platform’ is found in the work of the medieval Cordoban poet Ibn Guzman. The eighteenth-century British occupation of Tangiers may have provided an avenue for the importation of this lexical isolate, although the architecture of the octagonal garden pavilion now designated gazebo would have had multiple paths to Britain.
You can only read the first page at that link, but Dr. Techie at Wordorigins.org quotes a good chunk of the remainder of the article, which discusses two possible sources, North African and Hispanic Arabic qasbah ‘citadel’ and Ibn Quzman’s qushaybah. The discussion is interesting from both philological and cultural points of view.