You didn't specify any data structures you have for your polyhedron (e.g. adjacency lists/matrices between vertices, edges, faces), and this is a math site, so I'll only address the mathematical aspect of the question and not provide an efficient implementation with data structures.
Any two adjacent faces share an edge. A normal defines an orientation of a face, and thus of its edges. If you don't now the orientation of the edges with respect to their faces yet, either, you can determine the orientation a face normal induces on the edges as follows (you need at least something like an ordered list of the vertices to define the face): Traverse the edges (i.e. the vectors between consecutive pairs of vertices) of the face and add up the cross products of all pairs of consecutive edges; then the order in which you traversed the edges is or isn't the one corresponding to the normal according as the dot product of the sum of the cross products with the normal is positive or negative.
So that gives you the relationship between the choice of normals and the orientation of the edges these choices induce. Then you choose a normal on an arbitrary one of the faces and for a pair of adjacent faces where you've chosen a normal on one and not on the other, choose the other normal so that the induced orientations of the edges are opposite.