Gauss is probably the most famous mathematician today, his face even appears on one of European bills. But he did not have a charismatic personality, like Galois, nor was particularly interested in self-promotion, more of a recluse. Also Euler, Galois and Riemann had stronger influence on mathematics after them than Gauss did. So how did he come to be the "face" of mathematics to general public?
I was originally looking for the first documented reference of another contemporary mathematician calling Gauss the prince to no avail. What we do know is that he was considered, by at least many of his contemporaries (by some accounts all), to be the greatest among them.
I do see in The Beginnings and Evolution of Algebra, Volume 19 I. G. Bashmakova, G. S. Smirnova a citation that Disquisitiones Arithmeticae (1801) "...elevated him to the level of a leading mathematician of his time." In that source, the author states "He was soon to be referred as 'Princeps Mathematicorum'" (Prince of Mathematicians) after this time. This, at least by this source, dates the introduction of this title or nickname for Gauss.
It does not surprise me that his contemporaries thought of him so highly. For every great Gauss story that can be posted here, one more could probably be added. He was pretty active in a variety of fields and topics from the fundamental theorem of algebra, number theory, differential geometry, which according to Charles Boyer in A History of Mathematics c 1991 [pg 505], Gauss himself initiated, and the list goes on.
For current lack of a contemporary mathematicians ascribing this name to him, in Numbers - A Springer Publication c 1991 it is written that "After his death medals were struck in the Kingdom of Hanover at the initiative of the King on which he was described as 'Princeps Mathematicorum', a name by which he had already been called during his lifetime." Here are actual images of the coins. Note that on these coins I read, "MATHEMATICORVM PRINCIPI". Either way, close enough, it means the same thing.
Having your nickname printed on coins by a King at your death is one way to get a nickname to stick, although the coins may not have been necessary in the case of the great Gauss. He was so highly influential in his time, and he was never forgotten even to this very day.
He and Euler have been my two favorites since the earliest days of my personally being influenced by mathematics. It seems that social effervescence and a "charismatic personality" do not carry as much weight in mathematical popularity contests as it might in some other topic. Many of the greatest mathematicians (but not all) might be considered quite awkward individuals by common standards, yet they are the revered and commonly known individuals of our history.
Gauss portrait was printed on German paper money until recently (10 Mark note), before the introduction of the Euro. However my experience shows that the "general public" in many European countries does not recognize the people whose portraits are printed on their money:-) You can still buy some of these notes here http://www.kleinbottle.com/gauss.htm. (I understand that the rules of this site probably prohibit advertisement, but I think this is an exceptional case, anyway you may edit my message and remove the reference:-) This note is very well designed, showing some of the main achievements of Gauss in applied math and geodesy. Look at it carefully.
No other mathematician that I know (except Euler) was pictured on the money. (Hypparchus, the "father of astronomy", is depicted on some coins of his country, which on my opinion is truly amazing, and shows that in the Hellenistic world they also valued science).
Gauss is also known for his reluctance to publish. However at a very young age he pubished his book "Disquisitiones Arithmeticae", and this book is of such quality that it is still read by working mathematicians, and one of the recent Fields medalists, said that his main discovery is inspired by reading of this book (this is what he said himself).
Another achievement of young Gauss was a complete clarification of the question which regular polygons can be constructed by a ruler and a compass. This brought him immediate fame. Unlike the Disquisitiones, this question can be understood by any one with a primary school education. So he's got an unofficial title of Princeps Mathematicorum (King of Math), and a very decent position.
After that, he lived a long life, and published very little in Math (I mean little in comparison with Euler or Cauchy). His main work however was in astronomy and geodesy, and he computed the orbits of the newly discovered small planets. Again an achievement which "general pubic" can understand.
He also did a lot in Physics, invented the first working electric telegraph, etc. Having a very long career, and very diversified contributions, besides mathematics, attracted to him more public opinion than to some other mathematicians.
In my opinion, Euclid, Archimedes, Newton, Leibniz, Euler and Riemann perhaps had stronger influence on the development of mathematics, but these names are also reasonably well recognized by the (educated part of the) general public. I do not notice that Gauss's name is much more recognized than these 6.
Correction about money. Quick Google search shows many modern banknotes with Abel, Cauchy, Descartes, Euler, Newton, Luca Pacioli and Turing, not even mentioning coins.
In point of fact, Euler and Lagrange were the first mathematicians that held titles of that type. According to A. Weil ("Number theory: an approach through history", Birkhäuser Verlag, 1984):
(Chap. III, §III, p. 169): No mathematician ever attained such an undisputed position of leadership in all branches of mathematics, pure and applied, as Euler did for the best part of the eighteenth century. In 1745 his old teacher Johann Bernoulli, not a modest man as a rule, addressed him as "mathematicorum princeps" (Corr.II.88.92).
(Chap. IV, §I, p. 309): In 1745 Euler had been hailed by his old teacher Johann Bernoulli as "mathematicorum princeps", the first of mathematicians (cf. Chap.III, §III). By 1775 he clearly felt ready to pass the title on to Lagrange. "It is most flattering to me", he wrote to his younger colleague, "to have as my successor in Berlin the most outstanding geometer of this century"(loc.cit. Chap.III, §IX). Such was indeed by then the universal verdict of the scientific world. "Le célèbre Lagrange, le premier des géomètres" is how Lavoisier referred to him in 1793 in an official request to the Convention on behalf of his friend (Lag.XIV.314–315) at the onset of the Terror which was soon to claim Lavoisier himself as a victim. In the next century the title of "princeps mathematicorum" was bestowed upon Gauss by the unanimous consent of his countrymen. It has not been in use since.