I would like to know if the word "plot" would have been used in Victorian times (ca. 1880) to describe the story of a play, novel, etc. I've tried some online dictionaries with etymologies, but they only give the etymology, not when the usage as meaning a "story" began.
You need a dictionary with dated citations. OED is one such.
II. A map, a plan, a scheme.
6. The plan or scheme of a literary or dramatic work; the main events of a play, novel, film, opera, etc., considered or presented as an interrelated sequence; a storyline. Also in extended use.
the plot thickens : the storyline becomes more complex or convoluted; freq. in extended use.
1613 F. Beaumont Knight of Burning Pestle ii. sig. D4v, The plot of our Plaie lies contrarie, and t'will hazard the spoiling of our Plaie.
It's been in use in that sense (the main events or storyline of a dramatic work) since 1613.
Andrew explains well how to answer these questions, and demonstrates that the sense appeared well before then.
It is worth considering that words and senses do fall in and out of favour, and looking for closer cases is sometimes necessary (depending on just why we want to know).
Gustav Freytag's Die Technik des Dramas came out in 1863 and in English in 1900, just 20 years after your target date:
This same joyousness, and the sure perception of contrasts, allowed the poet, Sophocles, also to overcome the difficulty which his choice of fables prepared for him. The numerous and monstrous premises of his plot seemed peculiarly unfavorable to a powerful action proceeding from the hero himself. In the last hours of its calamity, it appears, the heroes are almost always suffering, not freely acting.
How did I find that? I looked up who was writing on the topic of plotting at the time.
Of course, the downside to this approach is that we know nothing of how usual a sense was from just this use. A book on plotting stories by a specialist on that topic, may use a word as jargon that would be unknown to the average educated person.
George Eliot's "Silly Novels by Lady Novelists" is about novels after all, was written in 1856, and I take a look and find that it uses "plot" only of the plans of characters, not of the author. This suggests it may not have been very often used in this sense.
(Why did I look there? Because it was an essay about stories that I knew about already).
But of course, one example that lacks a use is hardly evidence for the use not being made by others. And by good fortune, the anthology filed with the Library of Congress in 1883 that contains the essay in question has a an opening essay by the editor, which includes:
The novel with a purpose is fatal to the novel written simply to excite by a plot, or divert by pictures of scenery, or entertain as a mere panorama of social life. So intense is George Eliot’s desire to dissect the human heart and discover its motives, that plot, diction, situations, and even consistency in the vocabulary of the characters, are all made subservient to it. (Nathan Sheppard, ed. The Essays of George Eliot, 1883).
This is aiming at a "normal" reader, and has no qualms or hedging in using the term in consecutive sentences. I'd say 1883 is a good match to "ca. 1880", wouldn't you?
More to the point, the only part of this that needed special knowledge on my part was my knowing about that essay. If you're writing on the period you should hopefully have plenty of other essays you could have started with, and if not you could still have found uses, if perhaps not as fast. The same approach can solve other such questions. (19th C is especially easy; lots of printing but no remaining copyright means there's lots to be found on the web).
(If I hadn't thought of that Eliot essay first, I might have looked for contemporary reviews of Austen [though she wasn't thought to be very good at plotting by many of her contemporaries, contrary to the opinion of our time] or other novelists and playwrights of the time. The trick if we really want to know if a word was current, is think who would likely use the word, and look there).