I was getting ready to ship some cigars for a trade, and I realized that there were no threads that I could find on how to ship cigars safely. I went searching around on the web a bit and this is what I found:
(I'm still a newbie with cigars, but I worked for my mother packaging for her ebay business, and recently shipped 7000$ of fine bone china without cracking a single piece)

As with anything fragile, layers is the key here: put each cigar into a ziploc bag, making sure to remove as much air as possible.
4"x8" ziploc: 100 for 6$
http://metapot.com/product.php?productid=1794
100 baggies for $6, although you pay about another $6 in shipping. You could probably use regular ziplocs, but these are very good for cigars due to their size (fits up to five churchills snuggly) and I believe them to be a bit thicker, although I'd have to order some to make sure.

Be careful here if you're shipping multiple cigars. If the cigars are not wrapped in cellophane, it may be a good idea to go ahead and give each cigar its own bag. Cigars can have a tendency to rub against each other within the bag, thus chipping/tearing/ruining your cigars.

This part is optional, although I would recommend it:
Take the ziploc filled with cigars, and insert it into a bubble wrapped bag, or wrap it in bubblewrap. This gives the cigars a bit of protection within their box. The idea here is to wrap the cigars in something soft to protect them, and fill the rest of the box with whatever you want: packing peanuts are the best in my opinion, but newspaper will work fairly well.
Bubblewrap bags: 6 for $7
http://www.staples.com/office/suppli...93720#desclink
Bubblewrap:
Bubblewrap is something you don't really want to ship, just because its so big. I recommend Office Depot to buy it in smaller quantities. It runs about 6$ for a 15 square foot roll if you find the right brand.

If you choose to not bubblewrap the cigars: you still need to fill the box with packaging material. Packing peanuts are ideal, but newspaper can work just as well. I'm paranoid and think that newspaper will tend to settle and compress over long distances, so I prefer packing peanuts or massive amounts of bubblewrap.

Rule of thumb when packing something to mail: If you can shake it, they can break it. Essentially, once you're done packing, hold the box closed (don't seal it) and shake the box: if you hear something moving, add more packaging.

Now for your actual box: What we want to do here is get a slightly smaller box inside of a bigger box. It raises your shipping costs a little bit, but the boxes are free from USPS, and you could very well be shipping a lot of value in cigars! The idea with double boxing is that if someone hits the outer box it doesn't touch the cigars on the inner box because there's a layer of newspaper or some other packing material between the cardboard that you can see, and the cardboard protecting the cigars. How many times have you gotten a box with a nice half inch deep cut into the cardboard? Imagine if that cut was right over your poor stogies! Double box. It works like a charm. Generally we want a bit more space between the boxes, but we're not trying to isolate them from movement, just give them a bit more protection.

Boxes, both available for free from USPS in boxes of ten or twenty-five.
Small box "8.625" x "5.375" x "1.625"
http://shop.usps.com/webapp/wcs/stor...1645&langId=-1
Large box: 9.25" x 6.25" x 2"
http://shop.usps.com/webapp/wcs/stor...1643&langId=-1

Just a note: These boxes HAVE to be used for priority shipping through USPS. It may run a bit more expensive, but they're fast (2-3 days), have delivery confirmation/tracking and will insure your packages for pretty cheap ($1.10 per 100$ value last time I checked). I believe it will cost $4.60 with delivery confirmation if the package weighs less than a pound.
Note #2: USPS doesn't provide free tape anymore. They were having problems with people, quite literally, wrapping their packages in tape. The new boxes are designed to work without tape, but you should still tape them to be sure. One strip along the seams will be more than adequate.

The idea here is to package the cigars like you normally would within the smaller box, shake it to see if anything moves, then seal it up. Place the small box inside the larger box and surround it with packing material (newspaper, bubble wrap, peanuts, etc) although be aware it won't take a lot because these boxes are so close in size.

Once you have everything placed into the larger box, seal it up and slap a mailing label on there and its ready to go! This is my take on how to package cigars, and I take a very paranoid stance on packaging so if you choose not to use the whole method, the ideas are still the same. When I package for my trade I'll try to get some pictures so that you can see everything.

Other ideas:

Place the cigars into a ziploc bag, and tape the bag to the inside of the box. Saves supplies (read: money) while still protecting fairly well.
Pros: Cheap
Cons: If somebody happens to hit the spot where the cigar is...

Tubes!
http://www.cigarextras.com/index.asp...ROD&ProdID=152
Pros: They're protected. Really well!
Cons: At $3 a tube, this is a bad idea for large shipments.
I would recommend this for review passes, though. Whomever starts the pass ships in tubes, and the tubes go from person to person within the pass. You could probably use an envelope with these, or I would tape them to the inside of a box for better protection.

Humidity:
If you want to keep your cigars humidified during their cross-country journey, water pillows seem to be the way to go
http://www.cigar.com/cigars/viewciga...rod=M-HMC07-10
At 10 for $15, they're a pretty good deal if you're shipping a good bit. Again, this might be a good idea for review passes--just send one along with the box along with a couple tubes!
This should be considered a necessity if you're shipping to a different country

Did I miss anything? I want to work out the kinks and send this thread onto some of the other forums because I couldn't find anything very detailed anywhere... At least not that had links updated since 2004