If so many different hormones/molecules work by activating adenylyl cyclase, how do they have different effects?
How can hormones/molecules have different effects if they all work through cAMP? The short answer is that receptor expression on cell types is highly specific, and only if a cell has a particular receptor will it respond to a particular hormone. Thus two different hormones can have different biologic effects because the cells that contain those receptors are highly specific. Overall it is the presence of specific cellular receptors that determines the specificity of hormones and their effects.

A little more in depth of an answer... This is a classic concept from graduate physiology and was a real step forward in our understanding of hormone action in the 1950s/1960s. Earl Sutherland, who received the Nobel Prize in 1971 in Physiology or Medicine for this work, was on the faculty at Case Western Reserve University (and later at Vanderbilt University). Dr. Sutherland was studying the actions of hormones that were involved in glycogen metabolism (i.e. glycogen synthesis and glycogen breakdown). These classic studies identified a substance, now recognized as cyclic AMP (cAMP), whose intracellular concentration was increased in liver cells that were treated with hormones that stimulated glycogen breakdown. Conversely, cAMP was decreased by hormones or other conditions that were associated with glycogen synthesis. Most interestingly, it was identified that different hormones that either increased or decreased glycogen synthesis/breakdown had similar effects on the intracellular concentrations of cAMP (e.g. epinephrine, glucagon). This suggested that somehow cAMP was a common signaling molecule (or "second messenger") that transmitted the extracellular hormonal signal to the inside of the cell to have a biochemical effect (in this case stimulating glycogen breakdown). 

In the case of Sutherland's studies, the increased concentration of cAMP stimulated the activity of Protein Kinase A (PKA), and the lack thereof decreased PKA activity and allowed the actions of protein phosphatases to predominate. For example, when glucagon binds its receptor on hepatocytes (liver cells), that receptor is coupled to an intracellular enzyme ($G_S$) that is activated and then can activate an enzyme called adenylyl cyclase, which increases synthesis of cAMP from ATP. The increase in cAMP then binds to PKA and phosphorylates the glycogen synthesis enzymes and breakdown enzymes. When the glycogen synthetic enzymes are phosphorylated by PKA they are inactive and, conversely, when the breakdown enzymes are phosphorylated they are active. Thus, glycogen receptor activation leads to activation of the glycogen breakdown machinery and inhibition of the glycogen synthetic machinery. This makes sense physiologically if you think about it - glycogen acts to increase hepatic glycogen breakdown and increase hepatic release of glucose into the circulation. 

In brief, once Sutherland's group demonstrated the importance of cAMP as a second messenger protein within the cell, other groups began realizing that many other hormones led to changes in intracellular cAMP but each had there own effects. The differences in these effects were determined by the cell type that the hormone was acting on and whether or not that receptor was coupled to a particular second messenger system. Thus, you could have any number of receptors on the cell surface that are available to bind extracellular ligands (e.g. hormones, nutrients, drugs). However, each of these different hormones can be "coupled" or linked to different types of intracellular "second messenger" processes to transmit a signal. There are many types of second messengers that help transmit extracellular signals to the inside of the cell.

As you mention in the question, cAMP is a common second messenger system for a variety of different cell types. However, those different cell types have different receptors that are coupled to cAMP. Thus, hormones can have different effects depending on the tissues that express the receptors. For example, the glucagon receptor is expressed on hepatocytes which increases $G_S$ activity and thus cAMP, leading to glycogen breakdown and increased hepatic glucose production. Similarly, the $\beta_2$ adrenergic receptor that binds epinephrine/norepinephrine on smooth muscle is also coupled to $G_S$ which increases cAMP and leads to smooth muscle relaxation. These very different hormones have different biologic effects in different tissues, even though the effects are both driven by cAMP-dependent mechanisms. Briefly stated, it is the receptors that are present on a cell, that determine the response of a particular cell to that hormone. 

This is graphically shown in the image below from this medical biochemistry link in adipose tissue - though the same concept is true for liver cells. Glucagon signals through its receptor to increase adenylyl cyclase, cAMP and then PKA activity, while insulin inhibits that activation by increasing the activity of PDE (a phosphodiesterase) that works on breaking down cAMP and subsequently keeping PKA in its inactive form.