Conceptual and numerical issues related to the spectral factorization of polynomials and polynomial matrices with complex coefficients are studied in this report. Such investigation is motivated by the demand for reliable algorithms and CAD tools capable of solving latest signal processing problems involving complex polynomials. Basic concepts of the real polynomial spectral facorization theory are inspected first, and their generalization and necessary modification for complex polynomials then follows. Efficient numerical methods which are known to work in the real case are then revisited and their applicability for complex coefficients is considered. As an immediate result of this research, the powerful algorithms proposed in this paper have given rise to several routines implemented in the Polynomial Toolbox for Matlab and addressing the spectral factorization problem.