Aside from noise cancellation headphones, sometimes I wear silencing earmuffs (something like this: http://www.envirosafetyproducts.com/product/Bilsom-Viking-V3...). Most brands I've tried have been pretty equivalent, though some will probably be more comfortable for your head than others. Those, coupled with good earplugs* , usually tunes out most human speech around me.

* Earplug reviews here: http://www.slate.com/id/2118800/ My favorites are the Moldex Rockets, not listed: http://www.labsafety.com/search/Moldex/12675/?type=brand . Again, fit is at least as important as noise reduction; you want to be able to put them in and forget about them. Earplugs are quite cheap, so you may want to get a grab bag with two pairs each of ten or more kinds.

Alternatively, wearing headphones with pink noise (like white noise, but with less hiss: http://en.wikipedia.org/wiki/Pink_noise) works well, particularly if you can wear earmuff-style headphones over earplugs.

Here is a pink noise loop I made by stitching together the sample loop on wikipedia: http://shenani.gen.nz/~scott/pink_noise.mp3 (It's released under the same CC license as the sample on wikipedia, as a derived work.) Also, mirror it if you like it, as I am moving this week and in a day or two it will disappear.

Of course, not having a cubicle or open-air office is the better solution. (And not having loud neighbors.)

For more thoughts and studies on ambient noise ruining productivity, see _Peopleware_ by DeMarco and Lister.