How does a phonon cause two electrons to attract each other and form a cooper pair? We know that like charges repel each other. But my professor claimed that two electrons can attract each other as well. What he said was that due to screening an electron travelling at some speed won't repel another electron, but that they will, in some cases, attract each other due to weak phonon exchange. What does that mean? What is phonon exchange? Do two electrons really attract each other?
 A: Just as two oppositely pointed bar magnets (magnetic dipoles) attract, two electrons embedded within cancelling positive atomic charges can form transient electrical dipoles that attract. The catch is that to create such dipoles, there must be some form of "wobble" in the way that negative and positive charges are around the electrons.
A Cooper pair is a quantum version of just such a wobble-initiated dipole attraction. The effect that creates the wobbles is a quantized version of ordinary sound, also called a phonon. The synchronized way in which the charges wobble at each end of the Cooper pair is described in quantum terms as a "phonon exchange." Like two bar magnets rotating end over end in exact synchronization, this coordinated wobble dance enables the dipoles formed by the electrons to stay attached indefinitely.
Balancing all of this is the fact that these are conduction electrons, meaning they are part of "gas" of electrons that moves relatively freely within the neutralizing positive charge of the metal. If any pair of electrons gets too close to each other within such a gas, the neutralizing charges of the atomic lattice cannot move with them, and you start to develop a local negative charge in that region.
That charge buildup keeps the electrons in Cooper pairs from getting too close to each other, despite the attraction created by their phonon-coordinated charge wobble. This repulsion effect keeps the electrons in a Cooper pair surprisingly far from each, in the order of hundreds of atomic diameters apart. It is also why Cooper pairs are so delicate, since a mere dipole bond over those distances doesn't have much oomph. It can easily be broken by random vibrations (heat) that upsets the wobble dance.
The real magic in all of this, however, stems from a quantum effect that has no classical physics analogy of which I am aware. The two electrons -- or to be more precise, the two quasiparticle dipole pairs they form -- have half-integer spins, which makes them into mutually repulsive fermions. Once bonded, these half spins cancel each other, giving the overall Cooper pair spin of zero. Whole-integer spin makes Cooper pairs into a composite bosons, and such bosons can join together in a fully coordinated fashion that is quite impossible for fermions. All of the most remarkable properties of superconductors stem from that last seemingly minor point in the overall formation of Cooper pairs.
Addendum: @Danu pointed out this excellent illustration by Dr Ronald Griessen at Vrije Universiteit. It shows how rapid motion electron motion through an atomic lattice creates a lagging charge displacement, and thus a charge dipole. (Dr Griessen has some excellent online physics notes at that site, BTW.) 
Picture the box on the right as a (not to scale!) snapshot of a phonon-synchronized oscillation going on continuously between two electron sites, and you will have a pretty solid classical-analogy lock on how exchanging phonons (or in classical analogy, vibrating synchronously) can bind two electrons together:

A: From the Wiki article Cooper pair:

In condensed matter physics, a Cooper pair or BCS pair is two
  electrons (or other fermions) that are bound together at low
  temperatures in a certain manner first described in 1956 by American
  physicist Leon Cooper. Cooper showed that an arbitrarily small
  attraction between electrons in a metal can cause a paired state of
  electrons to have a lower energy than the Fermi energy, which implies
  that the pair is bound. In conventional superconductors, this
  attraction is due to the electron–phonon interaction. The Cooper pair
  state is responsible for superconductivity, as described in the BCS
  theory developed by John Bardeen, Leon Cooper, and John Schrieffer for
  which they shared the 1972 Nobel Prize.
Although Cooper pairing is a quantum effect, the reason for the
  pairing can be seen from a simplified classical explanation. An
  electron in a metal normally behaves as a free particle. The electron
  is repelled from other electrons due to their negative charge, but it
  also attracts the positive ions that make up the rigid lattice of the
  metal. This attraction distorts the ion lattice, moving the ions
  slightly toward the electron, increasing the positive charge density
  of the lattice in the vicinity. This positive charge can attract other
  electrons. At long distances this attraction between electrons due to
  the displaced ions can overcome the electrons' repulsion due to their
  negative charge, and cause them to pair up. The rigorous quantum
  mechanical explanation shows that the effect is due to electron–phonon
  interactions.

