Much Ado About Nothing is set in an aristocratic, hierarchical, and patriarchal society. So what do these words mean?
An aristocratic society is one in which both the majority of the wealth (and most of the means of generating that wealth, which in this case was land) and almost all of the political power was concentrated in the hands of a group of people who inherited their power, land, and wealth purely by virtue of their birth. These aristocrats (of which the king, prince, or ruling duke, such as Don Pedro of the play, were merely the highest level of aristocrat,) did not gain their wealth or power by their own merits (such as in a meritocracy), although men of ability were valued and could rise on their merits in certain situation, but rather they got their money and governing status simply by right of birth. This seems strange to most of us today, considering that there was very little provision if the person who inherited the title, lands, and government power were not suited to that position (or was evil, such as in the case of Don John!), but that was the world of the late Middle Ages and Renaissance Europe, of which Shakespeare wrote. Consequently, the people who belonged to the aristocratic class (and even sometimes those in the classes below them) began to believe there was something intrinsically better about them than the middle class (which was tiny by comparison to now at this time) or the peasants. This is reflected in some of the things the characters in the play say, such as when Claudio is horrified that Hero may have been unfaithful to him. Claudio is not only shocked by her lack of virtue, but that it would have been with Borachio, a mere follower of Don John and not a lord like himself, made it doubly bad in his eyes. There is definitely class snobbery in this play.
A hierarcical society is related to an aristocratic one, but there is a subtle difference. Not only is governmental power and societal precedence determined by one's position as part of the aristocracy or not, but there are levels of rank within that aristocracy that make a very big difference. For example, in the play, the Duke (Don Pedro) is a ruling prince (a sovereign of a state) -- he is referred to as the "prince" quite often, even though his rank is Duke. "Prince" was, at this time and as now, both a specific term (for the son of a sovereign, or, in some cases, a hereditary prince such as in Russia) and also a generic term for any sovereign ruler. Don Pedro (the term "Don" is sort of a generic Italian term for "lord") is at the apex of the aristocratic hierarchy. Below him is is bastard brother Don John (meaning John is the son of Don Pedro's father, but by a woman not his wife). This mean Don John inherited some aristocratic status from his father, but was not so elevated as Don Pedro, and could not inherit the sovreignty. There are further distinctions among the aristocracy, and a good clue is the order in which Shakespeare puts them in the Dramatis Personae. The highest is almost always listed first.
A paternalistic society is one that is ruled, governmentally and socially, by men. There is no doubt as to who holds governmental power and wealth in this play. Specifically, a woman's father decides who she should marry --- as Leonato and Antonio do for their daughters Hero and Beatrice, to some extent.