I'm currently enjoying a 30 day free trial to the Wall Street Journal Online, which saved me $1.50 in the airport last weekend when I saw a headline about how "fresh" your sushi really is.  Instead of blatantly violating copyright by pasting the entire article text below, I'll share a few tips...
NEVER  ON SUNDAY: Most restaurants do not receive fresh fish on the weekend, so it  is certain to be less fresh than on other days. In some places, Monday is even  worse.
 NEATNESS  COUNTS: Look in the sushi case at the bar. If pieces aren't wrapped and are  touching one another or the sides of the case, says Sushi Sasabune chef Nobi  Kusuhara, "they aren't really taking care of the fish very well."
 EXPECT  VARIETY: Offerings that change according to the season usually mean the chef  takes pride in his selections.
 GOOD  LOOKS: Fresh fish will look shiny. Tuna should not be dark or too red. "When  the color is red, almost as if it's been painted, ask if it has been smoked,"  says Mr. Kusuhara. If so, "it won't taste good and could be spoiled  inside."
 FOLLOW  THE CROWDS: Unpopular restaurants may not have enough turnover to have fresh  fish.
 SAY  NO TO SPICY SUSHI ROLLS: The spices are often intended to disguise inferior  fish.

Too bad we broke rules #1 and 6 last 
weekend.