Not necessarily traveling at light speed. (Although that would certainly count, I suspect traveling at the speed of light or nearly so is a 20th century thing.)
Very interesting would be a story in which the speed of light is mentioned as the maximum speed possible, but that is so depressing to many fans as well as being fairly sophisticated that it may have not shown up until, say, the 1950s.
The earliest concrete reference to the speed of light in science fiction I can find is A Thousand Years Hence; Being Personal Experiences as Narrated by Nunsowe Green, Esq., F.R.A.S., F.S.S., ex V-P.S.S.U.D.S. (Ex Vice-President of the Shoreditch and Spitalfields Universal Discussion Society), published in 1882. You can find the book at the Internet Archive.
By this great discovery of cross-electric speed, we were enabled to despatch the electro-light motor into far-off space, to overtake the ordinary light on its image or picture-carrying mission. It was not, however, until the further discovery of the Duplication of the Cross-Electric that we could bring back the over-taken picture — as, for instance, that of our little earth, as it was when the light quitted it so many years or so many ages past. Indeed, the vastly greater speed thus attained made us at last regard, with something like contempt, the old ordinary light-speed of about one hundred and eighty thousand miles in a second. But what a grand field, as we may suppose, now opened upon our ancestors, in bringing back the past aspects of the world! And these, as we shall afterwards see, could be restored by high scientific manipulation, even to the actual life dimensions.
Credit to the Historical Dictionary of Science Fiction for this one.
Note that this does not acknowledge the speed of light as an absolute limit; that would have to be sometime later, at least after the development of the Lorentz Group of transformations and Einstein's formulation of Special Relativity (both 1905).
In E.E. Smith's The Skylark of Space Chapter VII "The Trial Voyage" there is the following discussion of the spaceship's possible speed.
To hold down the power-plant, so that the bar won't tear through the ship when we cut her loose," replied Seaton. "Have you any idea how fast this bird can fly?"
"Well, I have heard you speak of traveling with the velocity of light, but that is overdrawn, isn't it?"
"Not very much. Our figures show that with this four-hundred-pound bar"—pointing to the copper cylinder in the exact center of the inner sphere—"we could develop not only the velocity of light, but an acceleration equal to that velocity, were it not for the increase in mass at high velocities, as shown by Einstein and others. We can't go very fast near the earth, of course, as the friction of the air would melt the whole works in a few minutes. Until we get out of the atmosphere our speed will be limited by the ability of steel to withstand melting by the friction of the air to somewhere in the neighborhood of four or five thousand miles per hour, but out in space we can develop any speed we wish, up to that of light as a limit."
"I studied physics a little in my youth. Wouldn't the mere force of such an acceleration as you mention flatten you on the floor and hold you there? And any sudden jar would certainly kill you."
So the characters are certainly aware that Einstein had calculated that mass would increase with velocity so that it would be impossible to reach the speed of light.
In Chapter VIII "Indirect action":
Regaining his self-possession as the wisdom of his friend's advice came home to him, Seaton sat down and pulled out his pipe. There was a tense silence for an instant. Then he leaped to his feet and darted into his room, returning with an object-compass whose needle pointed upward.
"DuQuesne did it," he cried exultantly. "This baby is still looking right at him. Now let's go—make it snappy!"[531]
"Not yet. We should find out how far away they are; that may give us an idea."
Suiting action to word, he took up his stopwatch and set the needle swinging. They watched it with strained faces as second after second went by and it still continued to swing. When it had come to rest Crane read his watch and made a rapid calculation.
"About three hundred and fifty million miles," he stated. "Clear out of our solar system already, and from the distance covered he must have had a constant acceleration so as to approximate the velocity of light, and he is still going with full...."
"But nothing can possibly go that fast, Mart, it's impossible. How about Einstein's theory?"
"That is a theory, this measurement of distance is a fact, as you know from our tests."
"That's right. Another good theory gone to pot. But how do you account for his distance? D'you suppose he's lost control?"
Smith first wrote The Skylark of Space between 1915 and 1921. The quotations are from the Project Guttenburg text.
This etext was produced from Amazing Stories August, September and October 1928. Extensive research did not uncover any evidence that the U.S. copyright on this publication was renewed.
Other notes and a list of corrections made will be found at the end of the book.
https://www.gutenberg.org/files/20869/20869-h/20869-h.htm#CHAPTER_V
So any earlier science fiction mention of the Speed of light or of Einstein's theory of relativity stating that the speed of light was the absolute speed limit will have to be published before The Skylark of Space in 1928.
David W.'s answer has a mention of the speed of light, but not as any sort of absolute speed limit, from 1882.
So the first mention of the speed of light in science fiction was in 1882 or earlier, while the first mention of the speed of light as an absolute speed limit would be sometime between 1882 and 1928.
The Skylark of Space was one of the earliest stories of interstellar travel but not the very first. So there are several possibilities to check for earlier mentions of the speed of light as a cosmic speed limit.
Already superseded by DavidW's answer (1882), but anyway worth a mention:
Two Planets by Kurd Laßwitz (1897) has the Martians mention their propulsion drive, and expecting to soon reach propellant speeds beyond the speed of light.
This mentions the existence of the speed of light, and the correct value, but not at all the idea that this might be a universal maximum speed - physics was still on the way that finally led to special relativity (see History of special relativity on Wikipedia.
