A plane-wave based algorithm is presented for the efficient evaluation of exact (Hartree-Fock) exchange. The theory and numerical results show that the method scales linearly with the number of plane waves. A new, in principle exact, procedure is also defined for the construction of the exchange potential within a Vanderbilt pseudopotential (PP) scheme. The present plane-wave+PP approach can be used in ab initio molecular dynamics (AIMD) algorithms employing exact exchange, thus significantly extending the range of AIMD methodology.