So when I 'import' an address, I have to put my private key into a textbox. Does this private key leave my machine and go out on the Internet?
Yes, but as long as blockchain.info is working properly it should be encrypted before it is sent out.
Blockchain clearly says they don't keep private keys.
Where does it say that? I'm nearly certain that blockchain.info stores all the private keys in encrypted form.
So where does this private key 'live' after I import an address into Blockchain.info wallet?
Unless they've changed their service recently (and I don't think they have), the private key is encrypted with your password in your browser, then the encrypted private key is sent to their servers where it is stored in their database.
Whenever you want to spend any bitcoins that require that private key, the encrypted form of it is sent from their database back to your browser where it is decrypted with your password and used to create the transaction.