'À la mode' meaning 'in the fashionable way'
The phrase à la mode has appeared in English in the sense of "according to current fashion" for hundreds of years. It occurs, for example, in "marriage à la mode" used by John Dryden as the title of a comedy (1673) and by William Hogarth as the title of a series of paintings (1743–1745); in both of these instances, the meaning of the phrase is "marriage in the up-to-date manner."
Merriam-Webster's Eleventh Collegiate Dictionary (2003) gives a first occurrence date of 1646 for à la mode in English. The first match that a Google Books finds is from John Gaudin, Ecclesiæ Anglicanæ Suspiria: The Tears, Sighs, Complaints, and Prayers of the Church of England (1659):
...though the palpable cunning of some men hath taught them to abuse of this credulous age, by shaving off the hair & primitive ornament of this Church, which was very good & graceful (having the honour of ancient, venerable and gray-headed Episopacy upon it) that they might the better induce Christianity, which is now above 1500 years old, to put on and wear (a la mode) the new peruques either of young Presbytery, or younger Independency (rather than Religion should go quite bald, and be ridiculous by its deformity and confusion;) ...
'Alamode' as a fabric
In the 1600s, alamode as a noun referred to a type of silk, according to Esther Singleton and Russell Sturgis, The Furniture of Our Forefathers, volume 2 (1906):
Alamode, a thin, glossy, black silk, is mentioned in 1676 in company with “Taffaties, Sarsenets and Lutes.”
The same material is mentioned in an account book from 1673, cited in Alice Earle, Two Centuries of Costume in America, MDCXX–MDCCCXX, volume 1 (1903):
We have ample proof that these black whisks [neck coverings] were in general wear in England. In an account-book of Sarah Fell of Swarthmoor Hall in 1673, are these items : "a black alamode whiske for Sister Rachel ; a round whiske for Susanna ; a little black whiske for myself."
Food-focused use of 'à la mode'
A Google Books search finds an example of à la mode in the context of food going back to a May 12, 1667 entry in Samuel Pepys's diary about a dinner he took at "a French house" maintained by his perriwig maker, Monsieur Robbins, in London:
...and in a moment almost had the table covered, and clean glasses, and all in the French manner, and a mess of potage first, and then a couple of pigeons a la esterve, and then a piece of bœuf-a-la-mode, all exceeding well seasoned, and to our great liking; at least it would have been anywhere else but in this bad street, and in a perriwigg-maker's house; ...
From Nathan Bailey, The Universal Etymological English Dictionary (731):
BEEF alamode [in Cookery] beef well beaten, larded and stewed with lemon, pepper, mushrooms, white-wine, &c.
From Hannah Glasse, The Art of Cookery Made Plain and Easy (London, 1747):
Beef à la mode in pieces.
You must take a buttock of beef, cut it into two pound pieces, lard them with bacon, fry them brown, put them into a pot that will just hold them, put in two quarts of broth or gravy, a few sweet-herbs, an onion, some mace, cloves, nutmeg, pepper and salt ; when that is done, cover it close, and stew it till it is tender, skim off all the fat, lay the meat in the dish, and strain the sauce over it. You may serve it up hot or cold.
Glasse's book also has recipes for "Beef à la mode, the French way" [a much longer recipe than the "in pieces" alternative], "Ducks à la mode" and "A goose à la mode." From the descriptions offered, it doesn't appear that any particular ingredient triggered the "à la mode" designation; the ducks and goose are cooked with red wine, the French beef with vinegar, and the beef pieces with broth or gravy. All call for onion (or shallots), and all involve "close pot" cooking at some point, so perhaps the stewlike result of the cooking is what these dishes have most in common. According to the Wikipedia article on Glasse, The Art of Cookery went through many editions and "continued to be published until 1843."
To similar effect, Elizabeth Raffald, The Experienced English Housekeeper (London, 1778) offers a promising lesson on "To a-la-mode BEEF." John Cooke, Cookery and Confectionary (London, 1824) includes options for "Rump of Beef à la Mode," "German à la Mode Beef," and "Beef Tails à la Mode."
William Kitchener, The Cook's Oracle, fourth edition (London, 1822) reports the existence of "Alamode Beef Shops" in London, dedicated to producing "this excellent dish" (beef à la mode), an observation confirmed by The Family Receipt-Book (1810) and mentioned in passing as early as 1795, in The Register of the Times (1795). Charles Dickens refers to beef alamode houses in David Copperfield (1850) and in several other of his writings. George Sala, Things I Have Seen and People I Have Known (1894) offers a fairly detailed retrospective view of such restaurants:
Forty, thirty, and even twenty years ago, alamode beef shops were scattered pretty liberally over central London, but the establishment with which I was most familiar was a house with the sign of the "Thirteen Cantons," in Blackmore Street, Drury Lane. ... Why it was called alamode puzzled me ; but it was a distinctly characteristic dish, deriving its peculiarity from the remarkably luscious and tasty sauce, or rather soup, with which it was accompanied.
In the United States, Mrs. N.K.M. Lee, The Cook's Own Book and Housekeeper's Register (Boston, 1832) offers three different recipes for "beef alamode." A somewhat similar recipe for "Veal à la mode" appears in House and Home; or, The Carolina Housewife, third edition (1855) by "a lady of Charleston [South Carolina)."
By 1868, the London publishing house of Longmans, Green, Reader, and Dyer was offering for sale a series of twelve books by Harriet de Salis applying à la mode to everything from soup (Soups and Dressed Fish à la Mode) to dessert (Puddings and Pastry à la Mode).
'À la mode' meaning 'topped with ice cream'
The first Google Books match for à la mode in the sense of "with ice cream topping" in a cookbook published in Berea, Ohio, in 1897. From Ladies of the Methodist Church & Ladies of the G.A.R., Berea Cook Book (December 25, 1897):
PIE A LA MODE
Any kind of fruit pie served with ice cream on top.
It seems unlikely that the ladies of the Grand Army of the Republic and of the Methodist Church in what is now a suburb of Cleveland invented this wording. There is, however, a very real possibility that "[fruit] pie à la mode" in this sense did originate somewhere in the U.S. Midwest, as references to it appear in memoirs set in—or cookbooks or magazines published in—Chicago, Illinois; Pittsburgh, Pennsylvania; Kansas City, Missouri; and Beloit, Wisconsin by the end of 1903. The only Google Books match from this period that mentions fruit pie à la mode in a publication not obviously connected to this region is from an article in American Kitchen Magazine, published in Boston in January 1903.
[[Update (September 26, 2017): Anewspaper database search turns up earlier instances of pie a la mode, starting with this one from "Fair Food Charges: What It Costs to Satisfy the Inner Man," in the [Aspen, Colorado] Daily Chronicle (May 25, 1893):
In all the main buildings of the World's Fair [in Chicago] these prices prevail for dinner, which is served from 11 a. m. to 4 p. m.:
Apple pie, a la mode...20[¢]
Collins ice cream........15[¢]
Other unique mentions of "pie a la mode" appear in newspapers in Greencastle, Indiana (June 13, 1895, reprinted from the Chicago Times-Herald); Washington, D.C. (July 26, 1895, in an account of a baseball game between the Washington team and the host Chicago Colts); Kansas City, Missouri (August 25, 1895; reprinted from the Chicago Tribune); and New York City (July 18, 1897, reprinted from the Chicago Record).
Again the connection to the U.S. Midwest—but now more particularly to Chicago, Illinois, is extremely strong.]]
The phrase à la mode was imported into English as a francophile (and therefore stylish) way of saying "in style." As Peter Shor notes in a comment above (and as the quotation from Pepys's 1667 diary confirms), à la mode was in use in France in the phrase "bouef à la mode" almost certainly before the anglicized "alamode beef" took hold in England.
As for à la mode in the sense of "ice cream topping," that meaning seems to have arisen in the U.S. Midwest by 1897, but not long before. (Evidently apple pie a la mode was featured on the dessert menu at the Chicago World's Fair of 1893, which undoubtedly helped its popularity grow rapidly.)