Apple maintains a table mapping your Apple ID to your iOS devices (probably by serial number but possibly by SIM card).
When you sell an iOS device, you should first turn off iMessage before restoring the software.
If you forget, though, or your iOS device is stolen, an alternative way to disable iMessages on the device is to go to apple's support page, log in with your Apple id, and you'll see all the devices apple has associated with that Apple ID. Then delete the iOS device you no longer want to have iMessages going to.
Apple support forum post describing this fix
Article I found via google which led me to the forum post