For something as commonplace as minor penalties, there are more than several sections to cover.
Rule 16 - Minor Penalties
16.1 Minor Penalty: Players assessed minor penalties are given a 2-minute seat on the penalty bench, more colloquially and affectionately known as the penalty box. Goalies are exempted from taking a seat in the box for a minor penalty; we'll cover those consequences when we get to Rule 27. (Spoiler alert: Goalie minor penalties are served by a skater on the ice at the time the penalty was committed.) While serving a penalty, teams aren't allowed to substitute for the penalized player.
16.2 Short-handed: Because a team can't substitute a penalized player on the ice, they're left with one less skater than their opponent, which leaves them "short-handed." If a goal is scored against a shorthanded team, the penalty with the least time remaining terminates immediately. So if there's only one penalty being served, then it's easy to figure out; on a two-man advantage, the guy with less time left leaves first because it gives a terrible advantage to the penalized team if the penalty with more time finishes first.
Imagine the Red Wings are on a 5-on-3 for 35 seconds. Patrick Marleau took a hooking penalty, then Joe Thornton took a diving penalty 1:25 later. (Yes, I know, just roll with it.) David Legwand scores 15 seconds into the two-man advantage. Then . . . Joe Thornton comes out of the box? Thornton would have had 1:45 left to serve, putting the Red Wings on a one-man advantage for that amount of time. If Marleau stays in the box, the Red Wings would have the one-man advantage for only 20 seconds, a 1:25 difference in power play time. So now you hopefully see that having the minor penalty with less time left expire first means teams aren't cheated out of their power play time.
Awarded goals count toward automatically terminating a minor penalty. Penalty shot goals do not. So if Legwand, in the above example, scored on a penalty shot on the two-man advantage (because we all know how likely it is that a penalty shot will ever happen on the power play), both Marleau and Thornton would have to stay in the box.
Believe it or not, there was a time when minor penalties were served for the full two minutes. For the 1956-57 season, the NHL changed the rule to allow a player to return to the ice from the penalty box immediately after a power play goal by the opposing team. Even in the '50s, the NHL was concerned about parity because according to Wikipedia (the only source I can find with anything to say on the matter), the 1950s Montreal Canadiens were just too dominant on the power play. Personally, I think the initial rule change was a dumb move, and I would like to see the NHL reverse this rule change. For all the want for more offense, this would be an easy change I'd be A-ok with.
If two players on the same team have minor penalties which terminate at the same time, the team captain tells the referee which player to let out first.
16.3 Infractions: Reference Table 2 on page 129 [PDF p. 140-141] has a list of all possible infractions that could result in a minor penalty.
Rule 17 - Bench Minor Penalties
17.1 Bench Minor Penalty: Penalties that generally are assessed against a team as a whole or non-player team personnel are bench minors. Any skater can be designated by the "Manager or Coach" to serve the penalty. All the same rules apply as with regular minor penalties.
17.2 Short-handed: "see 16.2."
17.3 Infractions: Reference Table 3 on page 130 [PDF p. 141] lists all possible infractions that could result in a bench minor penalty. A couple fun ones: Improper starting lineup (Rule 7) and Interference from the players' or penalty bench (Rule 56)
Rule 18 - Double-minor Penalties
18.1 Double-minor Penalty: This is the same rule as the minor penalty, except a skater serves the penalty for four minutes instead of two.
18.2 Short-handed: "see 16.2."
It doesn't seem to be written in this section of the rulebook (for what reason, I don't know), but I'll just state the obvious: If a team scores on the first half of their four-minute power play, the penalty with the least amount of time remaining terminates, in this case, the first minor. Since it's theoretically two penalties being served consecutively, a goal during the first two minutes doesn't automatically terminate the whole four minutes; instead, it terminates the first two minutes which are its own penalty, and the time starts ticking on the second half of the double-minor, or the second penalty if you prefer to think of it that way.
If you remember back in our discussion of delayed penalties, Rule 15.3 stipulated that if a goal is scored by the non-offending team on a delayed double minor call, the score sheet will list the penalty as a double-minor, but the goal wipes out the first two minutes of the penalty, and the last two minutes are served like a regular minor penalty. That section is repeated here: delayed call, double minor penalty, goal scored, first minor washed out, second minor still being served, official scoring listing it as a double-minor yada yada . . .
18.3 Infractions: Here are all the penalties that qualify for double-minors on their own: butt-ending, head-butting, high-sticking, and spearing. Otherwise, two minor penalties on the same player is the only other way to incur a double-minor.
I'll save the messy situation of coincidental penalties for next time. We know what happens if two players on the same team are assessed minor penalties on the same play. We also know what happens if the same player is assessed two minor penalties on the same play. But I wonder what happens if the same team is assessed more than one bench minor penalty on a play. First, could it happen? It's probably more theoretically possible than actually possible.
Imagine if Ryane Clowe were actually called for that interference from the bench, and also imagine that the Sharks had too many men on the ice at the same time, resulting in two bench minor penalties on the same play. So does Todd McLellan then have to send two Sharks players to the box? Or is he allowed to plop four minutes in penalties on one player? Does he have to do one or the other? Does it change depending on other circumstances? I don't know, and the rulebook doesn't seem to say anything about it. Oh well.