JHI's elegant lower bound of $8$ on $N$ is achieved by an explicit dissection.
I show my construction below; you might want to try to find
a solution yourself before proceeding $-$ it makes for a neat puzzle.
There may well be other ways to do it.
If somebody can make a "$3$-dimensional" graphic or picture of the
$8$-piece dissection, you're welcome to add it by editing my answer.
My diagrams are two-dimensional, labeling each piece with its height.
Fortunately the dissection is simple enough for this to be possible;
in particular, the eight pieces comprise four boxes and four L-shaped prisms.
This also made it possible to find the solution using just pencil and paper
on an otherwise uneventful international flight.
Begin by cutting the $6 \times 6 \times 6$ cube top to bottom
into three pieces, as shown in top view in the first square diagram.
Then cut each piece horizontally in two, dividing AB into $3+3$,$\phantom.$
C into $4+2$, and D into $5+1$. Each AB piece is then further subdivided
into a box B and an L-shaped prism A. The second diagram shows (say) the
bottom layer of four pieces, and the third diagram shows the top.
Note that the AB subdivisions are not quite the same.
(source)
Pieces with the same color will come together to form a smaller cube.
The larger C piece is a $4$-cube,
and the two A pieces form a $3$-cube as shown.
It remains to construct the $5$-cube from the remaining five pieces.
The last two diagrams show the bottom and top of the $5$-cube.
(source)
The two $5$'s are the larger B piece, rotated to span the entire
height of the cube, and the thick D piece.
The thin D piece completes the bottom, with width $1$.
The top is filled by the thinner C piece and the smaller B,
both rotated to height 4. QEF
I guess that a physical model won't make for a hard puzzle to reconstitute
into either one or three cubes (e.g. the AB, C, and D parts of the $6$-cube
are independent) but would still make a nice physical model of the identity
$3^3 + 4^3 + 5^3 = 6^3$.
This dissection is specific to the solution $(a,b,c;d)=(3,4,5;6)$ of the
Diophantine equation $a^3+b^3+c^3=d^3$; I don't know whether an $8$-piece
dissection is possible for any other solution. JHI's analysis shows that
one can never get below $8$, and in some cases even that's not possible:
if $a<b<c$ and $a+c<d$ then there's at least one corner of the $d$-cube,
say $(1,1,1)$, that contributes to the $a$-cube, but then any cell
$(x,y,z)$ with $\max(x,y,z) = a+1$ cannot connect to any corner.
This first happens for $(a,b,c;d) = (6,32,33;41)$.
What's the minimal dissection for the "taxicab" identity
$1^3 + 12^3 = 9^3 + 10^3$? JHI's corner-cutting argument shows
that at least nine pieces are needed.
An additional reference:
Chapter 12 in Problems and Snapshots from the World of Probability by
Blom, Holst, and Sandell is devoted to an elementary exposition of such
cover problems.
A related problem:
The solution to Problem 6556 in the American Mathematical Monthly
(Vol. 96, No. 9, Nov. 1989, pages 847-849)
looks at the average number of steps for a random walk to visit all the
edges on the cube in dimensions $d=2$, $3$, and $4$.
For $d=2$ the answer is easily computed to be 10.
For $d=3$ a system with 387 equations in 387 unknowns
is solved to give an answer of about 48.5.
For $d=4$ the problem is declared hopeless.
Best Answer
Let $a_n$ be defined by the recursion $$a_{n+2} + 4 a_{n+1} + a_n =0,\ a_1=-4,\ a_2=15.$$ Let $b_n$ be defined by the recursion $$b_{n+2} + 6 b_{n+1} + b_n =0,\ b_1 =-6,\ b_2=35.$$
The number of unfoldings of the labeled $1 \times 1 \times n$ cube is $-4 a_n^2 b_n$. (I might have a sign error here.)
We count spanning trees using the matrix tree theorem. Let $G$ be the dual graph to the $1 \times 1 \times n$ cube (so $G$ has $4n+2$ vertices). Let $V$ be the vector space of functions on the vertices of $G$. Let $\Lambda: V \to V$ be the Laplacian operator. Then $\Lambda$ has a one dimensional kernel -- the constant function -- and we are supposed to compute the coefficient of $t$ in $\det(\Lambda - t \mathrm{Id})$.
The cyclic group of order $4$ acts on the $1 \times 1 \times n$ cube by rotation around the long axis. This action commutes with $\Lambda$. So we can compute $\Lambda$ separately on each of the four eigenspaces of this rotation. The corresponding matrices are $$\begin{pmatrix} -4 & 1 & 0 & 0 & 0 & \cdots & 0 \\ 1 &-4 & 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 &-4 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 &-4 & 1 & \cdots & 0 \\ 0 & 0 & 0 & 1 &-4 & \cdots & 0 \\ & & & & & \ddots & \\ 0 & 0 & 0 & 0 & 0 & \cdots & -4 \end{pmatrix} \ \mathrm{on\ the} \pm i \ \mathrm{eigenspace}$$ $$\begin{pmatrix} -6 & 1 & 0 & 0 & 0 & \cdots & 0 \\ 1 &-6 & 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 &-6 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 &-6 & 1 & \cdots & 0 \\ 0 & 0 & 0 & 1 &-6 & \cdots & 0 \\ & & & & & \ddots & \\ 0 & 0 & 0 & 0 & 0 & \cdots & -6 \end{pmatrix} \ \mathrm{on\ the} -1 \ \mathrm{eigenspace}$$ $$\begin{pmatrix} -4 & 4 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0\\ 0 & 1 &-2 & 1 & 0 & 0 & \cdots & 0 & 0 & 0\\ 0 & 0 & 1 &-2 & 1 & 0 & \cdots & 0 & 0 & 0\\ 0 & 0 & 0 & 1 &-2 & 1 & \cdots & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 &-2 & \cdots & 0 & 0 & 0\\ & & & & & \ddots & \\ 0 & 0 & 0 & 0 & 0 & 0 & \cdots & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 & 4 & -4 \end{pmatrix} \ \mathrm{on\ the}\ 1 \ \mathrm{eigenspace}$$
The first two matrices are invertible and obey the recursions $a_n$ and $b_n$ respectfully. (See the recursive formula displayed in this article.)
The last matrix has a one dimension kernel. Taking the cofactor by deleting the last row and column, one gets a matrix whose determinant is $-4$, as can be checked from the same recursion as above.
Putting it all together, the number of spanning trees is $-4 a_n^2 b_n$.
I don't understand the statistical question you want to ask about the unfolded shapes.
Remark: Using the cyclic symmetry broght this computation down into the range of reasonable computation. But, even without that, I immediately knew that the answer would obey some linear recursion. Consider building a spanning tree of $G$ one layer at a time as we travel along the long axis of the cube. At the $k$-th partial stage, there are $4$ vertices of $G$ on the exposed boundary; call them $u_k$, $v_w$, $w_v$, $x_k$. The graph so far is a forest, each connected component of which contains at least one of the four exposed vertices. There are $15$ ways to group these $4$ vertices into connected components, one of which is actually impossible for planarity reasons. So there is some $14 \times 14$ matrix which records, for example, if the vertices on one level are grouped as $(\{ u_k, v_k \}, \{ w_k \}, \{ x_k \})$, how many ways are there to extend the forest to one where the vertices on the next level are grouped as $( \{ u_{k+1} \}, \{ v_{k+1}, w_{k+1}, x_{k+1} \})$. Taking powers of this $14 \times 14$ matrix and then pairing with some row and column vectors to handle end effects, you get this count.
This is what I learned to call the "transfer matrix method" (although Wikipedia seems to call something else by that name) and it solves almost all "linear" combinatorics problems.