Here's how pretty much every conversation about unwanted weight gain, gym memberships, and dieting has ever gone, for anyone, ever: 
Person 1:  I've been going to the gym and eating well, but the bathroom scale says I gained 10 pounds.
Person 2:  That's ok.  Muscle weighs more than fat, which means you probably gained muscle.
The simple answer:  It's true.  Muscle literally weighs more than fat. 

The more detailed answer:  First, let's get some terminology and semantics out of the way.  If I ask which is heavier, a pound of muscle or a pound of fat, most people will quickly answer, "They weigh the same amount, jerk."  Correct.  An equal weight* of two different things will always weigh the same amount, by definition.  However, they won't take up the same amount of space (volume) if they have different densities.  Density is mass** (or weight [though they mean different things {damn the English language!}]) divided by volume.  The same mass of a more dense material will take up less volume than a less dense material.  Similarly, the same volume of a more dense material will weigh more than a less dense material***.  Wikipedia says the density of human muscle tissue is 1.06 g/ml, while the density of human adipose (fat) tissue is 0.92 g/ml, which means that muscle is 15% more dense than fat.  Therefore, it's possible for the human body to lose a certain volume of fat and replace it with an equal volume of muscle, with an overall increase in weight.  The problem is that it's difficult (if not impossible) to measure muscle and fat volume without cutting people open, so attributing weight gain to the addition of either muscle or fat is completely pointless. 

*Weight and mass are used interchangeably in the English language, but it should be noted that weight is a vector force, while mass is a scalar quantity.  More at Wikipedia. 

**This issue is further complicated by the idea put forth in weightlifting magazines and nutritional foods of "muscle mass," which refers to the size (volume) of muscles (e.g. "massive muscles"), when the term should really be "muscle volume." 

***A practical example:  If your overall weight stays constant but you increase your mass of muscle, your overall volume will decrease (i.e. you'll look thinner). #health