I've always liked the interpretation Quillen gave in his "On the group completion of a simplicial monoid" paper (Appendix Q in Friedlander-Mazur's "Filtrations on the homology of algebraic varieties"). Here is a somewhat revisionist version.
Associated to a monoidal category C, you can take its nerve NC, and the monoidal structure gives rise to a coherent multiplication (an A∞-space structure) on NC. (If you work a little harder you can actually convert it into a topological monoid.)
May showed in his paper "The geometry of iterated loop spaces" that an A∞-space structure on X is exactly the structure you need to produce a classifying space BX, and there is a natural map from X to the loop space Omega(BX) that is a map of A∞-spaces, and is a weak equivalence if and only if π0(X) was a group rather than a monoid using the A∞-monoid structure. In fact, Omega(BX) satisfies this property, and so you can think of it as a "homotopy theoretic" group completion of the coherent monoid X.
What Quillen showed was that you can recognize the homotopy theoretic group completion in the following way: the homotopy group completion of X has homology which is the localization of the homology ring of X by inverting the images of π0(X) in H0(X). Moreover, the connected component of the identity in the homotopy group completion is a connected H-space, so its fundamental group is abelian and acts trivially on the higher homotopy groups.
In particular, if X is the nerve of the category of finitely generated free modules over a ring R, then X is homotopy equivalent to a disjoint union of the classifying spaces BGLn(R), with monoidal structure induced by block sum. The monoid π0(R) is the natural numbers N, and so you can consider the map
X = coprod_(n∈N) BGL_n(R) → coprod_(n∈Z) BGL(R)
to a union of copies of the infinite classifying space. This map induces the localization of H*(X), so the space on the right has to have the same homology as the homotopy group completion, but the problem is that the connected component of the identity on the right (BGL(R)) doesn't have an abelian fundamental group that acts trivially on the higher homotopy groups, so this can't be the homotopy group completion yet.
So this leads to the plus-construction: to find the homotopy group completion you're supposed to take BGL(R) and produce a new space, which has to have the same homology as BGL(R), and which has an abelian fundamental group (plus stuff on higher homotopy groups). This is what the plus-construction does for you.
Quillen's Q-construction contains within it the symmetric monoidal nerve construction (you can consider just the special exact sequences that involve direct sum inclusions and projections), but it's got the added structure that it "breaks" exact sequences for you. I wish I could tell you how Quillen came up with this, but this is the best I can do.
Best Answer
Can I be the first to recommend Elementary proofs of some results of cobordism theory using Steenrod operations, Advances in Math. 7 1971 29–56 (1971).
From the MR review: "In this important and elegant paper the author gives new elementary proofs of the structure theorems for the unoriented cobordism ring $N^\ast$ and the complex cobordism ring $U^\ast$, together with new results and methods. Everyone working in cobordism theory should read this paper."
The paper was revolutionary in (at least) two ways.