I may as well put my punt in here as well as your own code wasn't too far off from a solution. With a minor addition to the ON clause and the addition of DISTINCT you get the results you are after
select distinct a.state
from TableState a
inner join TableState b on a.city = b.city and a.[state] <> b.[state]
That
and a.[state] <> b.[state]
also handles the two cities with the same name in the same state scenario.
The fun starts when you also want to know which cities are in multiple states as you will then start to get results like
state city state city
state1 city3 state3 city3
state3 city3 state1 city3
Both rows are stating the same thing. But that's not what you asked for so I'll not start digging too deep!