Search on Amazon.com. I got a fully padded bag on there for about $30.
You can get them much cheaper online than in a store, and the padding's worth the extra money. Shell out for the padded bag, then do all the other stuff listed above. Can't get too protected, TSA cargo guys aren't known for being gentle.