The earliest known instance of the word 'news' being used to mean a report of recently occuring events was in 1423: "1423 Jas. I Kingis Q. clxxix, I bring the newis glad, that blisfull ben." However, it did not go into widespread use until after 1500. It was used as an abbreviation for newspaper largely in the eighteenth century, and, of course, as a shorthand for news on television or the radio from 1923 on: "1923 Radio Times 28 Sept. 9/1 10.0. -- Time signal, general news bulletin. Broadcast to all stations, followed by London News and Weather Report." (The very first Radio Times edition! It's certainly been going a while!)
The word newspaper first shows up in 1670: "in Westm. Gaz. (1900) 12 Sept. 2/3, I wanted ye newes paper for Monday last past." So what were newspapers called before the word newspaper was invented? It looks pretty clear from this and other examples in the early citations listing that they were called gazettes, which originally comes from the Italian gazzetta.
The first gazzette were published in Venice in the mid-sixteenth century. It was, after all, a hot bed of printing at the time. The OED reports that "similar news-sheets appeared in France and England in the 17th. The untrustworthy nature of their reports is often alluded to by writers of that period; thus Florio explains gazzette as
`running reports, daily newes, idle intelligences, or flim flam tales that are daily written from Italie, namely from Rome and Venice'."The earliest cited instance of gazette in English was in 1605: "1605 B. Jonson Volpone v. iv. (1607) M 3, O, I shall bee the fable of all feasts; The freight of the Gazetti."
The OED says that the origin of the word gazzetta is debatable: it may have been named for the coin with which it was paid for, or as a diminutive of gazza, meaning magpie.
Trivia: The OED's discussion of where the accent falls in the word gazzetta mentions William Cowper's Table Talk. Cowper's one of my favorite poets - always nice to see him get a mention.
Update: My father wrote to mention that Volpone is a book set in Venice, so its use of the word gazzetta is likely to have been use of local dialect to help flavor the ambiance.