this guy:

http://rouxbdoo.blogspot.com/2009/11/andouille-sausage-in-laplace.html

says these guy's andouille ships well because it does not need to be refrigerated:

http://www.cajunsausage.com/

Andouille is a smoked sausage.... the reason our ancestors smoked it was to preserve it when there wasn't refrigeration. Sometimes companies say to refrigerate something because they are afraid of a lawsuit. Sometimes stores put non-perishable items in the refrigerator because people expect them to be there and are more likely to buy them if they are refrigerated (pre-cooked bacon). Of course, sometimes it is really important to refrigerate something. Figure out which is which can be a challenge.

If you are really concerned you could get tasso. Which if I understand it correctly is andouille turned into jerky. Might be the perfect thing for backpacking!