Within the onscreen Star Trek universe, it had been long speculated that there were originally six galaxy class starships. Gene Roddenberry, the creator of Star Trek, confirmed the six ship theory. The flagship for the Federation has had a rather unsuccessful run as at least one half of the number produced have been destroyed.
The first ship of the six was the USS Galaxy, the prototype for the line of ships which bears its name. This ship has never been seen in the onscreen universe.
The second ship in the line was the USS Enterprise-D. Registry number NCC 1701-D, this ship was prominently featured in Star Trek: The Next Generation with cameos in the two latter series: Star Trek: Deep Space Nine and Star Trek: Voyager. The Enterprise-D was also featured in the movie Star Trek: Generations, where its battle drive section was destroyed above Veridian IV, and saucer section being unsalvagable on the surface of the planet.
The third ship in the line was the ill-fated USS Yamato. The USS Yamato made a quick appearance in the ST:TNG episode Contagion, as previously supplied by cberube.
The fourth ship in the galaxy class line was the USS Odyssey. The Odyssey appeared in the ST: DS9 episode The Dominion. The ship was part of the task force, comprised of the Odyssey and three runabouts, which traveled into the Gamma Quadrant in response to the newly discovered Dominion. The lack of support was a clear example of how underestimated the resolve of the Dominion was. A Galaxy class starship was more than capable of taking on its strongest peer belonging to the Alpha Quadrant races. A Jem'Hadar warship flew directly into the deflector array of the Odyssey and debris from the intitial impact hit the port nacelle, thus causing a fatal explosion destroying the ship completely. After this display, Starfleet quickly re-evaluated the place for such ships in the fleet. Shortly after this incident, the Defiant, Intrepid, and Sovereign class starships were comissioned, giving Starfleet a much more militant feel to it.
The fifth ship actually seen in the Star Trek universe was an undisclosed ship in the final episode of ST:VOY. Upon leaving the Borg subspace slipstream network, Voyager was shown cruising into a large fleet of ships. One of the ships was a Galaxy class starship. This was the only other time that a galaxy class ship was seen. No identifying features or onscreen dialouge were displayed to identify the ship.
The sixth and final ship in the Galaxy class is an unknown ship that has yet to be seen. However, according to Roddenberry, there was indeed a sixth ship. There is some speculation and possibly an onscreen reference to the sixth ship being destroyed in the battle of Wolf 359 by the Borg. Perhaps they are saving the final ship for a later appearance in the new UPN show Enterprise, the newest incarnation of the Star Trek universe.
Star Trek Encyclopedia
My own memory