In this paper, we consider solving the coupled systems of discrete equations which arise from implicit time stepping procedures for the linearized Navier-Stokes equations using mixed finite element approximation. At each timestep, a two by two block system corresponding to a perturbed Stokes problem must be solved. Although there are a number of techniques for iteratively solving this type of block system, to be effective, they require a good preconditioner for the resulting pressure operator (Schur complement). In contrast to the time independent Stokes equations where the pressure operator is well conditioned, the pressure operator for the perturbed system becomes more ill conditioned as the time step is reduced (and/or the Reynolds number is increased). In this paper, we shall describe and analyze preconditoners for the resulting pressure systems. These preconditioners give rise to iterative rates of convergence which are independent of both the mesh size h as well as the timestep and Reynolds number parameter k.