It has to be so common a question that the answer is actually given in various places on Dupont's own website (Dupont are the makers of Teflon):
“If nothing sticks to Teflon®, then how does Teflon® stick to a pan?"
Nonstick coatings are applied in layers, just like paint. The first layer is the primer—and it's the special chemistry in the primer that makes it adhere to the metal surface of a pan.
And from this other webpage of theirs:
The primer (or primers, if you include the “mid coat” in the picture above) adheres to the roughened surface, often obtained by sandblasting, very strongly: it's chemisorption, and the primer chemical nature is chosen as to obtain strong bonding to both the metal surface. Then, the PTFE chain extremities create bonds with the primer. And thus, it stays put.