I use newspaper only, and rarely have broken eggs. Usually it's when the box has been extremely mishandled. Otherwise, they do fine.
Ship the freshest eggs possible, and keep them cool and stored pointed end down.
I take a half-sheet of newspaper, and starting in one corner roll once, twist and turn it, and continue wrapping. It's hard to describe without pictures. But it creates a bubble of protective cushioning around the eggs. I then place them, pointy end down, in a box that has been lined with crumpled newspaper. Packing more crumpled paper on top, snuggly, so that when it's closed up, nothing moves. I've been shipping for a couple of years now, and it's working well.
Best part... we have a huge recycling bin in town behind the Borough building where they recycle all the unsold newspapers. It's clean, neat, and best of all, free.