Counting the unfoldings
If you consider your polyhedron as a graph, with one vertex per face, and two vertices connected if the corresponding faces are adjacent, if your polyhedron has no vertex such that the sum of surrounding angles is $2\pi$ then I would say the number of unfoldings corresponds to the number of covering trees of this graph quotiented by the symmetries of your polyhedron. This question on counting the number of covering trees of a graph provides some insight on this problem and therefore on the potential number of unfoldings you may get.
Computing one unfolding
If what you want is solely to compute one unfolding, then my strategy would be to use a breadth first traversal of the graph corresponding to your polyhedron to determine which adjacent faces should be kept glued in the unfolding. This technique is commonly used in algorithms for mesh parametrization in graphics, for texture mapping for instance. Roughly :
- take a random face $f_0$ and flatten in on the plane ;
- mark this face as done ;
- for each neighbouring face $f_i$ adjacent to $f_0$ :
- add $(f_0,f_i)$ to a queue ;
- mark $f_i$ as done ;
- while the queue is not empty :
- extract $(f_0,f_i)$ from the queue ;
- unfold $f_i$ rigidly next to $f_0$ ;
- for each neighbouring face $f_j$ of $f_i$ which is not marked as done :
- add $(f_i,f_j)$ to the queue ;
- mark $f_j$ as done.
Note however that this algorithm does not care on whether several unfolded faces overlap. I believe an example of a polyhedron which cannot be unfolded in a single piece without overlaps may be found, however I can't exhibit any which is compact. I believe this is related to surfaces with negative Gaussian curvature everywhere.