In this paper, we study the computational cost of solving the convection-diffusion equation using various discretization strategies and iteration solution algorithms. The choice of discretization influences the properties of the discrete solution and also the choice of solution algorithm. The discretizations considered here are stabilized low order finite element schemes using streamline diffusion, crosswind diffusion and shock--capturing. The latter, shock--capturing discretizations lead to nonlinear algebraic systems and require nonlinear algorithms. We compare various preconditioned Krylov subspace methods including Newton--Krylov methods for nonlinear problems, as well as several preconditioners based on relaxation and incomplete factorization. We find that although enhanced stabilization based on shock--capturing requires fewer degrees of freedom than linear stabilizations to achieve comparable accuracy, the nonlinear algebraic systems are more costly to solve than those derived from a judicious combination of streamline diffusion and crosswind diffusion. Solution algorithms based on GMRES with incomplete block--matrix factorization preconditioning are robust and efficient. (Also cross-referenced as UMIACS-TR-98-58)