I've been searching for this for ages but I just can't seem to figure out how it's done.

Maybe we can get a tutorial on it?

The twitter, facebook, last fm and some other clients can link to your contacts, so when you go to your address book it shows an entry with their lates tweet or last listened song in with their phone numbers and email addresses.

How do these apps manage to add the extra data in?

Have you taken a look at ContactsContract? http://developer.android.com/reference/ ... tract.html