Where did he get the idea of writing this story? where did he think of it.
Shakespeare used a handful of sources for Much Ado About Nothing.
Lodovico Ariosto, translated by Sir John Harington, Orlando Furioso (1591). Canto 5 of the poem provided Shakespeare with the marriage between Hero and Claudio and Don John’s plot to prevent it.
Matteo Bandello, La Prima Parte de le Nouelle(1554). The 22nd of Bandello’s novellas gave Shakespeare the setting in Messina, as well as contributing to the marriage plot involving Hero, Claudio, and Don John.
Matteo Bandello, translated by François de Belleforest, Le Troisiesme Tome des Histoires Tragiques Extraittes des Oeuvres Italiennes de Bandel (1569). Shakespeare could have used either Bandello’s Italian original or the translation and adaptation by Belleforest.
Baldassare Castiglione, translated by Sir Thomas Hoby, The Courtier (1588). This work was perhaps Shakespeare’s source for the romance between Beatrice and Benedick.
Hmm...that's a hard question to answer, unlike most of his plays, there doesn't seem to be much of a background with this one:
Although there has been some speculation that Much Ado about Nothing may be a heavily revised version of a play that Shakespeare wrote earlier in his career (a "lost" work that is often referred to as Love's Labour Won), Much Ado was probably written by Shakespeare in 1598 or shortly thereafter. Although scholars have attempted to trace the play's roots to Ariosto's tragedy, Orlando Furioso, to Bandello's twenty-second story from the Novelle, or to Spenser's poetic work, The Fairie Queen, in truth, no play ever existed quite like this one, with its interwoven plots, the wit and verve of Benedick and Beatrice, and the highly inventive comic element of Dogberry and his watch, which gives the Claudio-Hero plot most of its vitality.