Technically it is a galaxy not a nebula, although nebulosity is included within it, but "faint clouds" of stars/gas were refered to as "nebula" by Messier and others before the discovery of what they really were.
Some other info:
The Andromeda Galaxy, M31
The Andromeda galaxy, M31, is the nearest major galaxy to our own Milky Way galaxy. It is about twice the size of the Milky Way (old estimates = now we can include the 3,000 or so stars that used to be thought of a just part of M31's "halo" which is what scientists have used recently to revise the galaxy's size to triple what it was before), lies 2.5 million light years away, and is the most distant object that can be seen with the unaided eye. To find the Andromeda galaxy, first locate the Great Square of Pegasus using a sky map and then star-hop over to M31.
To the eye and in binoculars the Andromeda galaxy looks like a small, elongated "faint cloud." A modest telescope will show only the central portion of the galaxy as a featureless luminous glow. A very large telescope and good viewing conditions are required to see a hint of the underlying structure. However, even a small telescope will show that M31 is accompanied by two much smaller galaxies M32 and M110.
In the early part of the 20th century M31 was at the center of one of the most important discoveries in modern science. Early observers were not aware of the true nature of M31 and believed it to be a nearby gaseous nebula made up entirely of glowing gas. As a result, for many years M31 was known as the Great Andromeda Nebula (nebula is the Latin word for cloud). The development of long-exposure astronomical photography revealed the spiral structure of M31 and lead to the discovery of many more "spiral nebulae." The dynamic motion suggested by the shape of these objects lead some astronomers to believe that M31 was a solar system in the making. However, spectroscopic measurements revealed the Andromeda "nebula" was not a gaseous nebula at all but was in fact made up of a multitude of individual stars.
In 1923, Edwin Hubble found several Cepheid variable stars in photographic images of M31 taken with the 100-inch Mt. Wilson telescope. A Cepheid variable is a type of star that changes in brightness in a way that is directly related to the star's true brightness. By comparing the true brightness of these stars with their apparent brightness as seen from Earth, astronomers can calculate the distance of Cepheid stars. The Cepheids discovered in M31 enabled Hubble to establish that the "nebula" was not a nearby object but a galaxy far beyond the edges of the Milky Way.
Edwin Hubble went on to discover that the sky is full of galaxies all moving away from one another, thus revealing that the Universe is expanding.
Below an image showing the location of the galaxy.