i think the most important thing is that simple is better. assuming the mantids are nymphs, a plastic cup with mesh lid, or some tissue trapped under the lid is fine. twigs/perches/substrate etc are not necessary and will most likely cause harm to the mantis as they bounce around the container during transit. food is not really necessary if you feed them well prior to sending. this container should then be placed in the actual sending box, most suitably sized cardboard boxes will do fine so long as it is a bit bigger than the mantis container. pack the gap between the container and the box with something, i mostly use old newspaper. this is mainly for padding, but also some insulation. pack it so that the container cannot bounce around inside the box.
in this way, i have had mantids spend up to 4 or 5 days in transit and arrive alive and well, though this has been from country to country within europe. when i send mantids to other places in the uk they usually arrive the next day. i see you are in usa, i dont really know about your postal service but if packed well, the mantids can spend days in transit, so i dont think priority/next day shipping is really necessary. however i'm sure theres some usa guys here that know more about that and can advise you on usa specific postage issues.
