Joe Logic -- It's been a few weeks since the problem was posed; I assume that no satisfactory answers were received. Attached find my best effort: a pair of identical shapes which together will cover either cube or tetrahedron. (The parallelogram has sides of 2 and 2*sqrt(sqrt(12)), and height sqrt(sqrt(27/4)); through the center, rule a perpendicular to the length-2 sides, and trisect ... rule a square grid based on that. The parallelogram is cut on a 'stair-step' along the square grid lines. Sixty-degree lines starting at the figure's center mark the tetrahedron faces. The parallelogram will fold to cover the tetrahedron without cutting -- exchange the pieces vertically to form a net of six squares, which wraps the unit cube.) To make a (somewhat fragile) visual aid, one might attach one shape, via one of the unbroken stairstep edges, to one edge of a cube; and the other shape by one of the longer square-traversing segments to an edge of a tetrahedron (obviously the whole edge cannot be attached). Thus one could wrap either solid completely, with the other dangling by its hinge, or show each solid half-wrapped, or even superpose the two shapes to demonstrate congruency. (Not quite as elegant as the 2-D Dudeney puzzle which inspired it, alas -- and a zipper might be needed to close the wrap. Or at least snaps ...)

Greg Fredericksen -- Can a single shape be folded into both a tetrahedron and a cube? If by tetrahedron you mean regular tetrahedron, then I don't know. On page 246 of my book, I describe two pieces that together can be folded into both a tetrahedron and a cube. If the tetrahedron need not be regular, then there are a number of nets that can be folded into both a tetrahedron and a cube. See "Enumerating Foldings and Unfoldings between Polygons and Polytopes", Erik Demaine, Martin Demaine, Anna Lubiw, and Joseph O'Rourke, JCDCG 2000.

Martin Demaine -- I have been working on the same problem. See our page on Folding Polygons into Polytopes:

Koichi Hirata -- wrote an excellent program to compute the 'gluings' (where the edges match up) of a given polygon into a convex polyhedra.