So, if you've has sushi in the USA, you've had sushi that's been previously frozen. US regulations do not allow serving raw-from-the-ocean fish. For that matter, even in Japan, salmon is frozen before serving as sushi, because as a fresh-and-salt-water fish, salmon has multiple parasites that are directly transmissable to humans. Don't eat it raw.
Speaking from personal experience, I have had actual raw sushi while in Japan (some fish and shrimp were even killed in front of me). It does make a difference in taste and texture, especially for toro (fatty tuna) and ebi (sweet shrimp). Beyond that, it's a bit hard to tell the difference between the effects of freezing and the effects of quality differences in fish (I had raw fish in the Tsujiki fish market), and unless you can get "caught yesterday" fish you don't want it raw anyway; fish degrades quickly.
So, so sum up: if you have access to caught-this-morning, ocean-only fish (not salmon), you should try it raw for sushi, but previously frozen is still pretty good, and safer.