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 GriessnGriessen 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: