The Andromeda Galaxy was an inhabited galaxy located in the universe within relative proximity to the Milky Way. Andromeda had two satellite galaxies. (TOS: "The Corbomite Maneuver", "I, Mudd", "By Any Other Name")
A picture of the Andromeda Galaxy was on display in the briefing room of the USS Enterprise when the crew was reviewing star charts to search for the origin of an unknown buoy. (TOS: "The Corbomite Maneuver")
An ancient humanoid race from the Andromeda Galaxy became extinct following the destruction of their homeworld when their sun went supernova. Remnants of the species survived for a time on scattered outposts but eventually died out, leaving their android populations on their own. One of these android-populated outposts was the planet Mudd in the Milky Way Galaxy. (TOS: "I, Mudd")
Centuries ago, the Kelvans became aware of dangerously rising radiation levels in Andromeda, a development expected to make that galaxy uninhabitable for their species within 10,000 years (or 10 millennia). The Kelvan Empire dispatched expeditions of multi-generational starships to explore the neighboring galaxies for territories suitable for conquest and occupation. (TOS: "By Any Other Name")
Background information Edit
An older image of the Andromeda Galaxy appeared in the original "The Cage". This image was replaced for the remastered episode.
The distance between the Andromeda Galaxy and the Milky Way Galaxy was either about one million light years (Star Trek Encyclopedia, 3rd ed., p. 13) or about 2 million light years (Stellar Cartography: The Starfleet Reference Library ("Federation Historical Highlights, 2161-2385"); Star Trek: Star Charts (p. 10))
In Star Trek Online, it is revealed in the mission "Uneasy Allies" that the Iconians have rebuilt their numbers inside a Dyson sphere in the Andromeda Galaxy in preparation for an invasion of the Milky Way.