Basically, someone that wants to spend bitcoins sent to an address creates a transaction providing the public key of the address and signs the transaction using the private key. The address, public key, and signature are validated.
I want to add on to this as well. Being able to verify your address ownership like this is ONLY POSSIBLE IF YOU HOLD THE COINS IN A WALLET WHERE YOU CONTROL THE PRIVATE KEY. Far too many people are getting themselves in trouble by latching on to systems that don't give this access. I needed to verify one of my addresses before and it was one I had through Coinbase. Completely screwed me as I couldn't verify it since I didn't have the private key.
If you're ever in doubt as to whether or not you'll need to sign a transaction, make sure you have private key access. Coinbase and similar services are awesome when you don't need this, but keep safe.