We look at solving large nonsymmetric systems of linear equations using polynomial preconditioned Krylov methods. We give a simple way to find the polynomial. It is shown that polynomial preconditioning can significantly improve restarted GMRES for difficult problems, and the reasons for this are examined. Stability is discussed, and algorithms are given for increased stability. Next, we apply polynomial preconditioning to GMRES with deflated restarting. It is shown that this is worthwhile for sparse matrices and for problems with many small eigenvalues. Multiple right-hand sides are also considered.