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.
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:
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:
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).