The statement attributed to Gauss apparently first appeared in a biography of Gauss by the geologist Wolfgang Sartorius von Waltershausen, published shortly after Gauss's death:
W. Sartorius v. Waltershausen, "Gauss zum Gedächtniss." Leipzig: Salomon Hirzel 1856
On page 79, we find:
Die Mathematik hielt Gauss um seine eigenen Worte zu gebrauchen, für die Königin der Wissenschaften und die Arithmetik für die Königin der Mathematik. Diese lasse sich dann öfter herab der Astronomie und anderen Naturwissenschaften einen Dienst zu erweisen, doch gebühre ihr unter allen Verhältnissen der erste Rang.
My translation: "Gauss considered, to use his own words, mathematics to be the queen of sciences and arithmetic to be the queen of mathematics. While she would stoop to serve astronomy and other natural sciences now and then, she would be due first rank in all contexts."
No further information is provided as to when Gauss said or wrote this. The comparison with royalty is clearly based on the supreme rank mathematics is accorded among the sciences, and queen specifically may have been chosen to match the female grammatical gender of mathematics and arithmetic in German: die Mathematik, die Arithmetik.
However, this is not the first mention of mathematics as the queen of sciences one can find in the literature. This occurred (at least) two decades earlier in a text book for high-schools:
Andreas Neubig, "Grundriss der reinen Mathematik mit einer kurzen Anweisung zum Feldmessen," Bayreuth: Grau 1835
There we find the following in the introduction:
Die Mathematik, sagt Thiersch, ist die Königin der Wissenschaften.
Translation: "Mathematics, Thiersch says, is the queen of sciences". I note that this is from the third edition of Neubig's book. I was able to establish that the second edition was published in 1828. After a lengthy search, I was able to locate a scan of this edition at a Czech website, and was able to verify that the same sentence already appeared in it, on page 8.
Andreas Neubig was born on May 6, 1780 in Kulmbach. His dissertation was printed in 1811 by Adolf Ernst Junge in Erlangen. From 1821 to 1851 he worked as a Lyceal-Professor (professor at a high school) in Bayreuth. He died in November 1861.
The most likely match for the Thiersch in Neubig's book is Friedrich Wilhelm Thiersch. He was a philologist and educator born on June 17, 1784 in Kirchscheidungen and died on February 25, 1860 in Munich. He first worked as a professor at a high school before becoming a university professor.
Neubig and Thiersch are of the same generation and both resided in the Kingdom of Bavaria during their professional careers. The religious affiliation of both men appears to have been Lutheran. I haven't been able to find out whether they knew each other personally or whether they corresponded with each other, so it is unclear from what source Neubig quotes Thiersch. In 1825 the Bavarian king put Thiersch in charge of higher education, so he was presumably well known among Bavarian educators.
A potential source for Neubig's quote is the following publication by Friedrich Wilhelm Thiersch:
Friedrich Thiersch, "Ueber gelehrte Schulen. Zweiter Band," Stuttgart and Tübingen: J. G. Cotta 1827
On page 63 (my emphasis):
Mißlicher noch wird die Anordnung der zweiten Section, in der die mathematischen Wissenschaften, die physikalischen und also wohl auch die Naturgeschichte eingeschichtet wird, die zu der Mathematik in keinem näheren Verhältnis als zu irgend einer anderen Wissenschaft steht. Die Mathematik allein in der dürftigen Gestalt, in der unsre Universitäten diese Königinn der Wissenschaften kennen, gab nicht Stoff genug, eine Section zu füllen, und die Kunden der Natur, Physik, Mineralogie, Botanik, Zoologie wurden um so bereitwilliger zu ihr aufgenommen, weil sie an den übrigen Sectionen
der heiligen Vierzahl umherirrten, ohne darin Unterkommen zu finden.
My translation: "Even more unfortunate is the composition of the second department, which includes the mathematical sciences, the physical ones and therefore likely also natural history, which is not in a closer relationship to mathematics than any of the other sciences. Mathematics alone, in the paltry form in which our universities know this queen of the sciences, did not provide enough material to fill a department, and the subjects dealing with the natural world, physics, mineralogy, botany, zoology were accepted all the more readily in it as they strayed through the other departments of the holy quaternity without finding a place in it."
It is likely impossible to establish whether Gauss (or von Walterhausen, for that matter) was aware of what Thiersch had stated earlier.
