This is a result of Lickorish, in his paper "A representation of orientable combinatorial 3-manifolds".  The paper is only eleven pages, and is very readable.  In his proof, Lickorish rediscovers some ideas first investigated by Max Dehn 40 years earlier.  

Lickorish's theorem was unexpected at the time; I don't think that Witten's remark is really justified...

Here is a very sketchy overview of Lickorish's proof. 

The first step is to note that every closed, connected, orientable three-manifold $M$ has a Heegaard splitting.  That is, you can get $M$ by gluing together a pair of handlebodies.  (That this is true for combinatorial manifolds is an easy exercise.  That all three-manifolds are combinatorial is a very difficult theorem.)

The second step is to prove that any orientation-preserving homeomorphism of a closed surface is isotopic to a product of Dehn twists.  This requires proving that you can get from any (non-separating) curve to any other by a chain of curves, with each pair meeting exactly once. 

The third step is to relate Dehn twists to a special case of Dehn surgeries - this is probably the most "three-dimensional" part of the proof. 

Since the three-sphere has a Heegaard splitting in every genus, the theorem will follow.