There are several different dimensions of Sushi:
- Freshness: This is the most important in terms of flavor.
- Authenticity: If you want to make sure that the available (local) fish is at least prepared correctly, you will want to take a look at this item.
- Width of selection: This will tell you if the chef has the aspiration to serve customers who are familiar with Sushi instead of making a quick buck on something that is not really Japanese anymore.
Regarding freshness, you have to consider the respective country's import limitations for seafood. For example, Singapore, while being quite close to Japan, has very strict import limitations. So all fish, even if imported in the morning from Tsukiji fish market in Tokyo, cannot be served in most cases on the same day. It might have to be stored several days for customs and health check reasons. To the contrary, Hong Kong does not have such restrictions due to a very strong free trade policy. Sushi delivered in the morning from Tsukiji can be served the same day for dinner. This results in a vastly different quality of Sushi in Hong Kong compared to Singapore. So knowing the import restrictions of your country and the distances to the major fishing ground is a good base to find out if the Sushi across the border can be by default much better than in your current country.
While the fish does often not come from Japanese waters anymore, still a very large percentage is traded through the market in Tokyo.
Regarding authenticity, it is of course preferable to have a chef that is trained in Japan (which are to a very high percentage Japanese). Those can be found most easily in Japanese Hotels abroad (ANA or Nikko/Okura Chains). Since some of the hotels are not owned anymore by ANA or Okura, these might be difficult to find unless you know the history of the Hotels around you. The restaurants usually remained the same despite the change of ownership. Google can help here for example to find a former ANA hotel in Vienna with a still very high quality Sushi restaurant.
What has to be considered specially in Europe is that often Korean and Thai citizens open Japanese restaurants since Sushi can often generate a higher turnover than Korean or Thai cuisine. If a restaurant offers non-Japanese food it is usually a very good indicator that you are not dealing with authentic Japanese cuisine.
Another indicator is price. While not 100% reliable, you need to consider that Japan is a country with high living standards. While the competition among Sushi chefs in Japan forces many of them to seek employment abroad, many people who leave Japan are seeking a similar quality of lifestyle abroad. If the restaurant advertises permanently with discount prices, one should keep an eye open, since the authentic restaurants will much less compromise on quality than price.
Another good hint is if the menu is available in Japanese of course. It shows that someone in the restaurant speaks Japanese and that the restaurant is frequented often by Japanese people.
Width of selection
Authentic Sushi has an astounding width or selection that goes far beyond the standard fish selection that you find in many restaurants. However, since the cheaper restaurants catering to the casual Sushi-eater do not want to waste money on buying fish that the customers would not order since they do not know it, a selection beyond Tuna, Salmon and Shrimp is often a indicator that you are dealing with something more sophisticated.
Further it is always good to know the local names for fish and if they exist in Japan. Many foreign Sushi restaurant fall back on local fish that do not even exist in Japan and there the authenticity is gone quickly of course.
Customer density: It is good to know how many Japanese people are abroad per country to find out if there is a high likelihood of authentic Japanese restaurants.
Other information: If you speak Japanese, I would strongly recommend Japanese travel guides since they usually have very good information on these topics. On top of that, many countries have special magazines for Japanese expatriates. The local Japanese embassy might even advertise business run by Japanese citizens.