Very generally, replace every non-letter character with a space, then add a space before and after the whole string, then search for your two-letter state code by padding it with a space at the beginning and end. Your examples would turn into:

' John Smith of AZ '--> Matches with '% AZ %'

' John Smith of AZ Tucson ' --> Matches with '% AZ %'

' AZ John Smith '--> Matches with '% AZ %'

' John Smith AZ for Tucson ' --> Matches with '% AZ %'

' Utah Jazz ' --> Don't Match

' Azyme ' --> Don't Match

' Hazy ' --> Don't Match

As you can see, the state code will always be isolated in its own space.

For help on removing the non-letter characters, see here: How to strip all non-alphabetic characters from string in SQL Server?