The humorous exclamation my stars and garters! expresses surprise, excitement, etc.

For example, the following is from Unlike Sessions, Boehner going to pot, by Celia Rivenbark, published in the Dispatch-Argus (Moline, Illinois, USA) of Saturday 5^th May 2018:

Jeff Sessions must be wondering if the whole world has gone mad. Despite being appointed U.S. Attorney General, Sessions never seems far from the joyless, pursed-lipped tattletale of his youth.
In Washington, Sessions stands out like a ham hock in hummus with his red-cheeked outrage that is less fire and fury and more “my stars and garters!” I know his faux courtly type. They get agitated about all the wrong things: profanity in movies while casually cutting funding for preschool programs and making sure documented crazy people can buy guns.

In this exclamation:
– the noun star denotes a badge, typically of precious metal, in the shape of, or ornamented with, a star, worn as part of the insignia of an order of knighthood or of chivalry;
– the noun garter denotes the badge of the highest order of English knighthood, i.e., the Order of the Garter.

These are, in chronological order, the earliest occurrences of the humorous exclamation my stars and garters! that I have found:

1-: From The Upholsterer, or What News? A Farce, in Two Acts. As it is performed at the Theatres Royal in London and Dublin (Dublin: Printed by William Sleater, 1758), by the Irish playwright and actor Arthur Murphy (1727-1805):

My Stars and Garters! what a sudden Evolution here is in Things?

2-: From The Upholsterer, or, What News? A Farce, in Two Acts. As it is Performed at the Theatre Royal, in Covent-Garden. With Alterations and Additions (London: Printed for P. Vaillant, 1763), by the Irish playwright and actor Arthur Murphy (1727-1805):

What the Devil is here to do now;—I am all over in a Quandery. […] Oh my Stars and Garters! here’s such a piece of work—What shall I do?

3-: From The Tim Whisky: A Journey to Oxford, published in The London Magazine: Or, Gentleman’s Monthly Intelligencer (London, England) of August 1765:

The six-foot hostess at the Bear,
Toss’d up her nose, and head in air,
“Supper at such an hour!
My stars and garters! who would be,
To have such guests, a landlady,
That had it in their power?”

4-: From A Poetical Dialogue between Goody Gracious and Lucy Loveall, published in The Oxford Magazine: Or, University Museum (London, England) of May 1770:

Goody Gracious.
Thus frighted, from my chair I ’rose,
And (wou’d you think it?) from my nose
THREE drops of blood—ah, THREE! (no more)
Dropp’d singly down upon the floor:
[…]
No soul could be in WORSER case.
Lucy Loveall.
My stars and garters! case indeed!
Why what a thing your nose should bleed!

5-: From Liberal Opinions, Or the History of Benignus (London: Printed for G. Robinson, and J. Bew, 1777), by Courtney Melmoth, pseudonym of the English author Samuel Jackson Pratt (1749-1814):

In gratitude, (—here he put his hand on his breast) there is much joy,—In liberality, (he looked respectfully at Mr. Draper) there is still more; and we hold, sir, the second place of felicity, as receivers of benefits; that you may hold the first, as the person who conferred them,—He paused.
My stars and garters! cried Mr. Draper, what a pity it is, Sudberry, you and I are strangers!
[…]
She […] asked me if I did not love letter-writing. I told her, in reply, that I loved reading and composition passionately, but that I had as yet few correspondents, and therefore few occasions to write letters. Oh gracious and gemini! (answered this voluble girl) now that is to me altogether amazing.—Of all things in the world, I love writing, next to that I love talking, and next to that riding round the Parks. Oh, my stars and garters, and blue ribbons! What a rapture there is in sending and receiving long letters.

6-: From The Eccentricities of John Edwin, Comedian. Collected from His Manuscripts, and Enriched with Several Hundred Original Anecdotes. Arranged and Digested by Anthony Pasquin, Esq. (London: Printed for J. Strahan, [1798])—John Edwin (1749-1790) was an English actor; Anthony Pasquin was the pseudonym of the Irish painter and engraver John Williams (died 1818):

In our days ambition erects her garish banners in every town and village of the kingdom, and pride impels the peasant to tread upon the heels of the peer—Every woman we meet expects to be distinguished by the appellation of Lady, which is now generally conferred on all females, from a duchess to a dairy-maid […].
[…]
Every woman on the sabbath, however mean her condition, considers herself as legally entitled to such honors, and never fails to shew symptons [sic] of mortification, if she is not dignified as a lady;—having studied the vocabulary of affectation, she imagines it is polite to screw up her mouth, till the aperture resembles a small purse, and then mumbles thus;
“Mem—purdigious—veastly—axquisite—
“My stars and garters its quite the Bung-tun.”
And many other words equally well pronounced, and equally well applied.