How do we know the stars orbiting Sgr A* are orbiting a supermassive black hole and not just the center of mass of the Milky Way galaxy? It is my understanding the best evidence we have for Sgr A* being the black hole at the center of our galaxy is the incredible velocities of the stars orbiting around it. But wouldn't the stars similarly orbit the center of mass of the Milky Way? Not nessesarly needing there to be a black hole there? 
 A: Gravity obeys something called Gauss' Law, which states the gravitational acceleration is proportional to the mass enclosed.  So even though the total mass of the milky-way is very large, when you're very near the center, the mass effecting gravity is much smaller.  The gravity from everything outside of the enclosed area ends up (roughly) canceling out.  The same applies to other objects, like the sun or earth: if you were to tunnel down into either, the gravitational acceleration would decrease.
A: Objects orbit around their barycenter. The barycenter always is closer to the more massive object. If the difference in masses is very great, it can be inside the more massive object (such as the Earth/Sun barycenter being inside the Sun).
But the barycenter also can be outside any one object in a gravitationally bound group.  If there are many objects and they are roughly the same mass, one would expect objects in the group to interact with one another in more complicated and difficult-to-predict ways than if there were a single massive object at the core.
Such is the case in Globular clusters, which are spherical groups of stars that may in some cases orbit their group barycenters.  Predicting or even studying the trajectories of individual stars in these clusters is complicated by the n-body problem, the vast computational resources necessary to plot gravitational interaction of 3 or more objects. Stars in globular clusters have been observed following unusual paths that may change shape with time.
The motion of stars around the galactic core of a spiral disk like the Milky Way is more regular than the motion of stars in globular clusters.  This is one indication that a single massive object is the attractor at the center of the Milky Way. 
A: In addition to the other answers given, I should add that the energy we observe from the GC is that of either some very exotic mass like a boson star, or of a supermassive black hole. We know mathematically a black hole is much more likely to form than these sorts of objects. Here is a diagram showing the progress in nailing this down over time with Schwarzschild radii for the estimated mass of the SMBH on the top of the x-axis, and density of the central mass on the y-axis. Astronomers have essentially nailed it down to being in the top left portion of the below:

(Schoedel et al., 2003)
Recent observations show with increasing precision that it is indeed a SMBH. This is of course disregarding our recent photographic evidence of a black hole.
Active galactic nuclei (AGN) show properties that are very indicative of a black hole, e.g. the jets which are emitted by the black hole.
The highly centralized mass is also shown by hypervelocity stars (members of binary systems orbiting close to the SMBH which are disrupted and fly out of the galaxy at hundreds of kilometres per second). We know hypervelocity stars come from this situation because the number density of young, hot stars is very high near the galactic centre. Conditions arise such that the production of new O and B type stars is common, and we know already that binary systems are already common throughout the universe.
Finally, we observe tidal disruptions which involve tidal ripping of stars which get too close to the central black hole, and by looking at enclosed mass as a function of radius from the GC, we see that it flattens out at $r=0$, which indicates again the centralized mass.
I hope this answer provides enough detail, without necessarily going into mathematical detail. 
