I'm currently working on a program that takes a bunch of STL files as input (and metadata on how many copies of each file are wanted) and returns a single new STL file that contains all of the input STL files, nicely stacked for 3D printing. My goal is to minimize the volume of the bounding box.
My current heuristic approach is to take each input file, and rotate it so the bounding box volume is minimal. Now I treat the parts as if they are cubes. I then sort the parts by volume and place the largest first, then the smaller ones (the idea being that any gaps left by the larger ones will be filled up by the smaller parts). I try to place each part (in positive space) as close the origin as possible. I fill up three arrays with x,y,z coordinates of the corners of the boxes already place and then consider any combination of these as location for my new box. If it does not fit in the current bounding box, I pick the location that leads to the smallest increase of the bounding box.
However, this does not always give satisfactory results. The algorithm is more than fast enough, but most often the placement is just really bad and I could do far better by hand.

Maybe treating the parts as boxes is just not good enough. Another option would be considering convex hulls for the parts but that would be a lot more difficult to implement and I've got no idea what kind of algorithm you would use for packing convex polyhedra.

Maybe I need to consider different orientations of the boxes I am currently using. Maybe just rotating each 90 degrees will help?
However, this leads to the time becoming non polynomial (not good, since I usually need to consider over 100 parts) and I can't use dynamic programming either since there is no good way to measure how much space is still available.
Perhaps another option is just to pick a random orientation (rotated about 90 degrees), each time a part is inserted?

This is a really complicated topic but I'm interested if anyone here can tip me off to some resources.

This is just a sample output:

Density is 9% which is not good enough to get the Shapeways discount. Manually I can easily make it to over 10%. It's really annoying because the computer stacking looks much more dense than the one I made myself, but it's not.

Does your program put gaps between pieces so they don't get printed as one?

That does look really tight and dense. Could you post a pick of how you would place the parts so we can see what can be improved?

That would be useless since I'm taking advantage of the natural geometry of the puzzle to stack them. A computer can't possibly do that, I just want it to stack it in some way that is efficient enough.

This is how I would do it myself. As you can see there is a large gap between the core and the other pieces, so I think it shouldn't be too hard for a computer to improve upon it, or at least, match it.

I have found that on my (very) simple designs the quickest route to 10% density is just to "open up" the puzzle so that the pieces are separated enough for the Shapeways printing process. This may leave internal spaces where the core is, but it usually works.

I think that this sort of stacking exercise you are trying to do would be very difficult to program and would be very processor intensive. Good luck! Perhaps you should concentrate on getting your software to take an "assembled" stl file and just pull it apart?

BTW, this task seems related to my job. I do PCB design, and there is an Autoroute option on the software which is very clever, and can do hundreds of tracks in a few seconds. But ... it takes a long time to set up the parameters correctly so it does a good job and can complete 100%. Usually, it cannot route a few tracks, which have to be done manually, and the tracks it does do are often very weird. I usually can always do a better job manually.

Tom, the only improvement I can see off your current method would be to utilize different geometry patterns that are space filling. you say you take the bounding box for each individual part, why not make the boxes different three-dimensional shapes? Its possible that utilizing shapes like a trapezo-rhombic dodecahedron or patters like cubeoctahedron's + octahedron may be better suites for space filling. The second option seems like the best candidate for me, because a puzzle always parts of varying size, and it may be useful to "stuff" the little parts in the octahedrons.

Other than that, I think you may have to try a completely different approach. Maybe its possible it simulate each part a little larger that it actually is (by half the minimum distance that must be kept between adjacent parts) and simulate dropping all the parts into a box one by one?

I think the 1D version of this problem is called the Cutting Stock Problem which is NP-Hard. So this is by no means an easy problem, especially since you're adding 2 more dimensions and aren't necessarily using nice clean rectangular bounding boxes.
3D version is called Packing problem, but most of what I've seen for that is for boxes or spheres.

Don't know if you using these terminologies in your search for algorithms, but I know from past experiences, it can be incredibly hard to find what you want until you know what it's called.