I have done it both ways, marking it with Fragile and Eggs and Perishable, Handle with care. I have also left the box blank. I have very few ruined shipments. The two I have had have gone to California. I now caution anyone in CA who wants my eggs that my experience in shipping there has not always been good. I did have one shipment that only one egg broke. I sent some with an unmarked box at the buyers request and he got 2 eggs out of 8 that were unbroken. The box was crushed the carton holding the eggs was damaged as well. In these cases, I think it is the result of going through major postal handleing centers where everything is more automated and boxes are not handled by many people. Machines can't read our lables or lack thereof.
Like Cyn, I spend a lot of time packaging my eggs and I send extras because of occasional breakage.
If you feel you seller failed to adequately package your eggs you should let them know and leave feedback to that effect after you notify the seller.
I am sorry you had this experience it really is dissapointing.