Smells and fragrances work because tiny molecules from the object we're detecting get released into the air and carried into our nose. Tiny little receptors up near the back of the nostrils recieve these molecules as an input and send an electric signal to our brain which we interpret as smell. Now it turns out that charcoal is particularly good at absorbing these smells (in fact Buck Weimer has even begun marketing clothes containing charcoal to absorb unpleasant biological smells). But how does it work?
The answer is that charcoal has a huge surface area. Although a lump of charcoal looks like one little piece, if you zoom in the surface of a charcoal lump is filled with holes, tubes and craters (it is, after all, based on plant matter) which means a single gram of charcoal can have several square meters of surface area, all wrapped up into a tiny lump. Invisible to the naked eye, but a small molecule can easily navigate them.
The next effect is that two objects naturally cling to each other. What's called the London force effect (or, to give it its older name: the Van der Waals effect) two particles will naturally cling to each other because of the temporary charges dancing around on their surfaces. We don't notice this effect most of the time because it's very subtle. A marble on a table is easily picked up by the human hand, but we actually have to overcome a nanoscopic London force to separate it from the table. What this means is that small objects will cling to each other very, very well.
So charcoal works by having a lot of surface area, which small particles go colliding around on. This constant interacting between the charcoal's surface and the tiny particles leads to an overall "stickiness" to charcaol. Kind of like if we were to throw a dozen balls into a hedge, a lot of them would get caught up and tangled on the branches. Thus, charcoal (or anything with a large surface area) can absorb smells!