Krylov subspace
Suppose the only thing you can do cheaply with a giant matrix A is multiply it by a vector. What can you build from that one operation? Starting from b, you can form Ab, then A(Ab) = A^2 b, and so on. The Krylov subspace of dimension k is the span of these: K_k(A, b) = span{b, Ab, A^2 b, ..., A^{k-1} b}. It is the natural arena for any method whose only tool is the matrix-vector product.
Why is this the right search space? Because polynomials in A live here. Any vector in K_k is p(A) b for some polynomial p of degree below k. So searching K_k for a good approximate solution of Ax = b is the same as asking which polynomial p makes p(A) b closest to A^-1 b. The Cayley-Hamilton theorem even guarantees that A^-1 itself is a polynomial in A, so for k large enough the exact solution lies in the Krylov subspace.
Modern iterative solvers are, almost without exception, Krylov methods: conjugate gradient, GMRES, MINRES, BiCGStab. They differ only in which vector of the growing subspace they pick (minimize the residual? make the residual orthogonal to the space?) and how they build an orthonormal basis for it cheaply via Arnoldi or Lanczos.
The power of the idea is that the subspace dimension k stays small while n is enormous. If the eigenvalues of A are clustered, a low-degree polynomial can already make p(A) b an excellent approximation, so the method converges in far fewer than n steps. This clustering is exactly what preconditioning tries to manufacture.
The Krylov subspace is exactly the set of vectors reachable as a polynomial in A applied to b.
The raw basis b, Ab, A^2 b, ... is useless to compute with directly: the vectors all tilt toward the dominant eigenvector (that is the power method) and quickly become nearly parallel, so the basis is severely ill-conditioned. Arnoldi and Lanczos exist precisely to orthogonalize it.