Optimal pebble-packing shape
The title of the New Scientist article Ricky cited in the comments is "Pyramids are the best shape for packing":
Graduate student Alexander Jaoshvili of New York University and his colleagues filled and shook containers of tetrahedral game dice. They found that the tetrahedra were packed tightly enough to occupy 76 per cent of their containers. In comparison, randomly packed spheres fill up to 64 per cent of space, while the figure for squashed spheres, or ellipsoids, can be as high as 74 per cent.
Here is an image from an article in the Economist on this work:
A relevant paper is http://cherrypit.princeton.edu/papers/paper-217.pdf ("Improving the Density of Jammed Disordered Packings
Using Ellipsoids"), which tries varies ellipsoids in simulation and comes to the conclusion that having all three axis have different lengths is best. The intuitive explanation given is that what pieces really need to be able to pack well is to be able to change shape, and the closest solid pieces can come to shape-shifting is rotation, so the more they change under rotation the better, with spheres being the worst shape from that perspective. The best ratio of axis lengths appears to be 1.3.
(Fig.1B added by J.O'Rourke.)
Also relevant is http://cherrypit.princeton.edu/papers/paper-291.pdf ("Distinctive features arising in maximally random jammed packings of superballs"), which tries out various superballs, going from concave all the way to cubes. The summary is that cubes seem to work best, but the simulator can't actually handle them. The intuition appears to be that the rounding results in dead space, because the pieces line up by faces anyhow.
Putting those two results together seems to imply that the best shape would be 1 by 1.3 by 1.7 bricks (which have the bonus that .3 + .7 = 1, so they might really line up nicely). I mailed one of the authors asking if my understanding of the above papers is correct, if it means that such bricks would work better, and if the next step is to make physical models and test them because the simulators can't handle them, and his answers were yes, probably, and yes.
As Brendan McKay and Aaron Golden pointed out in the comments, the density of these packings is extremely protocol dependent in experiments (that is, it matters a lot how exactly you throw and shake the particles). I believe a better defined question would be the "jamming"-type problem studied in the paper mentioned in my comment. (For readers who would like to know a little bit more about what I mean about jamming, see my answer to Joseph O'Rourke's previous question). In jamming, there are many shapes that jam at densities higher than spheres; aside from the paper I cited above, you can see section 5 of the really quite nice review by Martin Van Hecke that I mentioned at the end of my previous answer. I don't know that anyone has searched for the shape that jams at maximum density in this paradigm though, and to me at least it is not as of high physical interest. This is because the particular density at the transition for each shape is not expected to be "universal" for this jamming transition, whereas quantities like the dependence of the various elastic constants as one approaches the transition are apparently universal.
Let me now get off my soapbox and give some evidence for my first paragraph by returning to the experimental situation of throwing bodies into a container and shaking until little changes. Here is a reference related to the paper cited in the comment by Ricky Demer which yields rather different results.
Baker and Kudrolli also did a series of experiments in 2010 on packing of various shaped dice under various protocols. Their results on the volume fraction are here:
Their comment on the paper of Jaoshvili et al is "Experiments on random packed tetrahedronal dice have been reported recently in Ref. 16. Volume fractions were said to be $0.76\pm.02$ if the observed packings were extrapolated to infinite systems, but the protocol by which the packings were prepared was not clear."
Actually, back in 2006, Yu, An, Zou and Kendall wrote a simulation / experimental paper which explores various vibration and packing protocols; they claim that they can get balls to pack into close-packed configurations consistently. Despite only showing data for packings of balls, it has the intriguing comment "This packing method can also produce densest packing for nonspherical particles. For example, for cubes, we obtained $\rho_{max}\approx1$, and interestingly 1D, 2D, and 3D vibrations produced comparable results. "
The above is by no means exhaustive, there are many other such protocols and papers with a broad variety of results.
edit: While I'm editing this I may as well upgrade an old comment of mine to the question to a paragraph here. One thought is that (depending, again, on precise definitions) cubes or other space-tiling polyhedra might be able to achieve a packing density of 1 before they completely jam.
The 2012 paper by F. Smallenburg, L. Filion, M. Marechal, and M. Dijkstra, Vacancy-stabilized crystalline order in hard cubes Proc Natl Acad Sci USA 109:17886–17890 performs event-driven molecular dynamics and Monte Carlo simulations of hard cubes in a box (presumably periodic, though this is nowhere explicitly stated), see also the commentary by Daan Frenkel here. The main result of the paper can be summarized in this "phase diagram" (Fig. 5):
For low volume fraction $f<0.45$, the cubes are unjammed and form a fluid (F). When $0.45<f<0.50$, one begins to see "coexistence", i.e. cubic crystalline chunks in the fluid or fluid droplets embedded in a cubic crystal. For $f>0.50$ the system forms a (possibly slightly rotated) crystal with some vacancy defects which lasts up to $f=1$. This is some evidence that cubes jam when they fill space.
Here are images from the Supplementary Information showing simulation snapshots at various values of $f$ (Fig. S1).