Of American-English origin, the phrase the icing, or the frosting, on the cake denotes:
– an additional benefit to something that is already good;
– an attractive but inessential enhancement.

This phrase refers to icing and frosting in the sense of a mixture of sugar with water, egg white, or butter, used as a coating for cakes or biscuits.

The earliest occurrence of the frosting on the cake that I have found is from a short story, by one Howard Fielding, published in The Galveston Daily News (Galveston, Texas) of Monday 16^th December 1889:

Her Captivating Smile.
The Story of a Bashful Young Man and a Baker’s Maid.
The Painful Uncertainties of Flirtation Across the Street and the Perils of Faint-Hearted and Unnecessary Delay.

[…]
[…] I ventured to bow, and though it was not returned I could see that I had given no offense. After that I bowed regularly every morning, and also in the afternoon when I went away.
I think it was three weeks after this that she waved her hand. This was the frosting on my cake of joy.

Her Perpetual Smile.—illustration for Her Captivating Smile—The Galveston Daily News—16^th December 1889:

 

It seems that, in the following advertisement published in the Jackson Daily Citizen (Jackson, Michigan) of Monday 31^st March 1890, the frosting on the cake is part of an extended metaphor—however, I have not found what W. M. Bennett & Son were selling:

HAPPY
TO
SEE YOU,
LADIES
AND
GENTLEMEN
OF
JACKSON
And vicinity,
TUESDAY
AND WEDNESDAY
AT THE
GRAND ELECTRIC!!
We make a
DISPLAY!
A
SPECTACULAR
PRODUCTION

With charming music by Prof. Boos’ Orchestra mornings and evenings. It will in no way interfere with our great sale, being the frosting on the cake, the scollops on the edge of the pie, the whipped cream of the eclaire, the chocolate and bon bons of fashion which gives one a great appetite and causes the plate to be passed a second time.
It will all be done by

ELECTRIC LIGHT.

You’ll think you’re in a palace and you’ll have a good time, and you’re most cordially invited.

W. M. BENNETT & SON,
CEASELESS
TOILERS.

The earliest instance of the icing on the cake that I have found is from The News and Observer (Raleigh, North Carolina) of Tuesday 7^th April 1896:

“YE DEESTRICT SCHOOL.”
The Funniest and Most Successful Entertainment of the Season.

The wheels of time turned back fifty years for an hour last night, and brought back to recollection “Ye Deestrict School” of ye olden tyme. And it was decidedly the most successful revival this country from the Capitol to Ramkhatte has ever seen.
On this frame-work of the old country school was hung a fabric of natural humor and merry fun, of whose changing variety the audience never tired.
[…]
The school was divided into three sections: The morning session, the school recess, and the afternoon session. […]
[…]
The afternoon session was the climax, the “icing” on the cake. It was as full of fun as the house was of folks.

In the following paragraph from The Times (Philadelphia, Pennsylvania) of Monday 26^th July 1897, the icing of the cake is used metaphorically:

So far as sugar forms the icing of the tariff cake it may be taken to represent many a cool million.

In the following theatrical review from The Examiner (San Francisco, California) of Tuesday 24^th January 1899, the icing on the cake means the best:

Much to the enjoyment of a packed house and a contented box-office, “The Wizard of the Nile” wizzed [sic] his waggish way through three cheerful acts of music and nonsense, at the Columbia last night. Like the small boy with the icing on the cake the Daniels management saved the best for the last bite.

The second-earliest occurrence of the icing on the cake that I have found is from the Democrat and Chronicle (Rochester, New York) of Thursday 4^th April 1901:

Reflections of a Bachelor.
New York Press.

When a girl first gets engaged she never believes her mother ever could understand how she feels.
A girl’s training is the icing on the cake; sometimes it’s a mighty different flavor from the rest of it.
It comes as natural to the average woman to tempt a man as it does to put most of her clothes on over her head.
No old bachelor’s reputation is ever safe with a woman unless she thinks she has got a chance for him herself.
A woman with a rainy-day skirt on looks about as attractive as an angel with chin-whiskers and a market basket on his arm.