How can odors be removed from bricks?
Background info:

I recently started collecting Duplo blocks to build toys for our sugar gliders (small, exotic marsupials); I've also got some regular Lego blocks in the mix that my boyfriend's had for who knows how long.  To get the most for my money (especially when it comes to avoiding figurines and random pieces that don't suit my purpose), I've been buying large lots of Duplos off of e-bay (all of them are specifically Lego brand - you couldn't pay me to use Mega Bloks or other crummy knock-offs, lol).

Our gliders are our babies and on top of that, I've got high-end breeding pair (ie rare colorings/genetics) and a "pet only" pair that cost a combined total of $1800 - in other words, their safety is a HUGE concern for me and I'm adamant about cleaning and sanitizing any Duplo blocks I buy as soon as they arrive.  Also, gliders can't be potty-trained and inevitably use my Duplo creations as toilets... meaning pee sometimes gets in the crevices between blocks.  To top it off, they scent-mark everything.  As a result, I've got to disassemble the toys I've built and re-wash them 1-2x a week to keep things sanitary.

Like toddlers, gliders tend to "taste test" their toys at times (and even if they don't, they walk all over the Duplo blocks and then eat with their hands and groom themselves with their tongues).  That means I have to use cleaning products that are very safe, yet still effective (particularly when it comes to odor control, as gliders really do stink things up!).

My cleaning method:

The way I've been washing the Lego Duplo and regular Lego blocks is to fill a clean kitchen sink with a 50/50ish mixture of hot water (hottest the tap can provide, that is) and white vinegar, then add the blocks.  I soak them for a few hours or possibly overnight, then scoop them into a large colander*, rinse them thoroughly with warm-to-hot water (iirc 104F+ is "unsafe" for Legos; hence why I mix the really hot water and the vinegar together before adding the Legos) and lay them out on towels to dry (inside, with a box fan blowing across them, flipping them over every few hours until they're totally dry).  If anything is particularly soiled, I use the soft (ie non-scrub-pad) side of a clean sponge to give the blocks a gentle scrubbing as they soak in the warm vinegar water; for anything stuck in difficult-to-clean crevices, I use a baby bottle brush and/or q-tips.

*Based on a recommendation I saw on this site, I ordered a salad spinner to spin-dry my Duplos and regular Legos (and bunny veggies and dinner salads)... best thing ever - I LOVE it.  GET ONE!

Vinegar is very popular as an odor eliminator for a WIDE variety of odors.  It was the first and only cleaning method I tried because - despite all the pet odor eliminators and pet cage/habitat cleansers on the market - the vast majority of glider owners stick to a simple 50/50 blend of water and vinegar.  It's very effective for removing urine, feces, scent marking oils, stuck-on (sugary) foods, etc. and all the related odors from glider toys and cages (not to mention bunny and cat litter boxes)... plus it's dirt cheap, gentle, pet (and child) safe and doesn't leave residue behind.

Because I haven't actually had to get cigarette smoke odor off of Legos and wanted to see if I could find some info to back up my hunch that it would work on that as well, I just did a cursory Google search for "remove cigarette smell with vinegar" and got a ton of hits confirming that it's very effective.  I then searched specifically for info about using vinegar on Legos and found an article that provides some great tips and additional information on using vinegar to clean/deodorize Legos (and the article really focuses on difficult-to-remove cigarette odors) - http://www.brickwarrior.com/?p=1