Fish is a collective name for a series of decks, usually blue with the occasional splash in another color and utilizes cheap creatures, usually of the type Merfolk, and countermagic to keep the opponent at bay.
What Fish decks have in common is they are meta-decks, designed to beat what they will play against. Fish's biggest advantage is its adaptability, and Fish can be tuned to win against almost any deck. A player playing with Fish must therefore have a lot of cards, since their build will vary over time, and have a good eye for which decks that will be played during the next tournament. The name Fish comes from an old Extended deck which was built around merfolk, counterspells and Standstill. The deck won by making it hard for the opponent to make anything productive until all the small creatures had killed him. When Fish was adopted into Vintage, the merfolk one after one dropped from the lists, but the name remained. Fish decks can be in any color or combination of colors, but usually include blue to be able to play Force of Will. Fish also often includes some power-hate, such as Chalice of the Void or Null Rod. From there it's totally up to the deckbuilder to include cards that will do well in the current meta. Good Fish decks are proactive decks, that plays creatures that will make it hard for your opponent to play, like Meddling Mage, while they slowly beat him to death.
Nufish is an updated fish deck that has a few tutor effects, and utilizes Jace the Mind Sculptor, along with a relatively large number of creatures including Dark Confidant and Trygon Predator as both win conditions and board control. This particular deck list won the 2010 Gen Con vintage event.
NuFish deck: