I guess you be passing in a parameter of the value everytime the user updates the value calling the method each time so you could do something like this:
-- DECLARE @yourSearch varchar(max);
-- This will be passed in your server side code
    SELECT *
    FROM AddressBook
    WHERE pid LIKE '%@yourSearch%' OR 
          tag LIKE '%@yourSearch%' OR  
          address1 LIKE '%@yourSearch%' OR 
          address2 LIKE '%@yourSearch%' OR 
          city LIKE '%@yourSearch%' OR 
          stateProv LIKE '%@yourSearch%' OR
          postalCode LIKE '%@yourSearch%'
This will get all the substring matches if you want to find a exact match you could do something like this:
SELECT *
FROM AddressBook
WHERE @yourSearch IN (pid, tag, address1, address2, city, stateProv, postalCode)
Please note you said ALL so i queried it even against the id of the
  address which i would of thought you would not want the user to see
  but i kept it in there just incase - delete every instance of pid if
  you don't want the id returned in the query and specify your columns
  names instead of *