You add the link to the message in a email address and then when they click on it, the unsubscribe.php file (or whatever it is) unsubscribes the email address using the $_GET variable in the link
e.g.
$emailmessage = "<a href=\"http://www.yoursite.com/unsubscribe.php?email=".$emailaddress."\">http://www.yoursite.com/unsubscribe.php?email=".$emailaddress."</a>";
And then in unsubscribe.php you have a line like:
$unsubscribe = mysql_real_escape_string($_GET['email']):
$query = "DELETE * FROM database WHERE email = '".$unsubscribe."'";
Of course you'd need to check for SQL injection etc.
You might also want to add a random number and store it in the database along with their account details so people just can't guess email addresses and try to unsubscribe random people. You'd need to add that to the link in the email message and check for it in the database too.