The answer depends on just how pedantic you want to be.
Space Travel Vehicles With Some Basis In Scientific Reality
As Terdon has already pointed out, the first vessel used to travel through space in a manner vaguely similar to scientific reality was probably the "projectile" (Jules Verne's own name for it) in From the Earth to the Moon. However, as Verne's nomenclature suggests, this wasn't so much a spaceship in the sense that we think of such things, but an actual projectile, like an oversized artillery round.
As I understand it (which should be taken with a grain of salt, since I haven't read the book), this device functioned in more or less the same way any other projectile does - someone shoots it out of a gun or cannon of some kind, and the projectile (and whatever or whoever is inside of it) goes in the direction in which the gun was pointing. In other words, the passengers were not driving the projectile, they were merely along for the ride.
Furthermore, it appears that Verne never actually referred to his "projectile" as a "spaceship" or "spacecraft". However, the term "space-ship" was used to describe the projectile in an article written in 1880 about the book in question; this article was published in the "Pall Mall Gazette".
Jules Verne's "projectile"
Vehicles Actually Referred To As Spaceships
Apparently, the first author to use the word "spaceship" himself in a story was actually J.J. Astor1, in a novel called A Journey in Other Worlds, published in 1894; and from what I have found on the subject, this was the first depiction of a space vehicle which was actually piloted by the people inside of it (as opposed to a hollow shell being fired out of a cannon, leaving the occupants to pray that it didn't go off course and send them hurtling through space forever).
The credit for 'spaceship' in the sense of “a manned spacecraft” usually goes to J. J. Astor’s 1894 novel A Journey in Other Worlds, a futuristic tale set in the year 2000. However, space-ship also appears in an 1880 Pall Mall Gazette, in reference to Jules Verne.
J.J. Astor's "spaceship"
Space Travel Using Rockets
The first fictional account of rockets being used to travel to space may have been written by the Russian polymath Konstantin Tsiolkovsky, who was actually a scientist, among other things. Most of his work was true scientific research and theory, but he also wrote several science fiction stories, largely aimed at a younger audience. Included among these is a novella written in 1893 titled On the Moon. It could be argued that Tsiolkovsky was the first author to bring a formidable dose of scientific reality to space travel stories; his more serious work is still highly respected in academic circles to this day.
Note: Thanks to Hypnosifl for suggesting that I add this to my answer
And Arthur C. Clarke claimed that The Other World: Comical History of the States and Empires of the Moon by Cyrano de Bergerac, published in 1657 (after de Bergerac's death), invented the concept of ramjet technology being used for space travel.
Note: Thanks to rand al'thor for suggesting that I include this in my answer, and to J... for providing the information in his own excellent answer.
Space Travel Of Any Kind Using Mechanical Devices
Incredibly, the first reference to space travel in a mechanical device of any kind is literally ancient (although we can't actually call it science fiction, since such designations didn't exist in the ancient world):
One of the earliest examples of something similar to science fiction literature is ancient Indian poetry such as the Hindu epic Ramayana, which describes ancient flying machines or “mechanical birds” [Note: as has been pointed out in the comments, these devices may have been more like chariots than birds, although there is evidence for both interpretations] that could travel through air, earth and even fly into outer space. While not being even remotely realistic, the design of these “mechanical birds” illustrates a belief that space travel could be achieved in mechanical means rather than magic or godly intervention. Interestingly, these ancient flying machines, as the reader will see, are much more sophisticated than many of the travel methods created by science fiction authors in the medieval era or even the enlightenment.
Another early source that has certain elements of science fiction and space travel is The Ebony Horse, one of the stories from the One Thousand and One Nights. In particular, the story features a mechanical horse, which is capable of space travel. Once again, this example is not that imaginative, however, it illustrates the spreading belief in the possibility of space travel using purely mechanical means.
The "mechanical horse" from The Ebony Horse in One Thousand and One Nights.
In the first half of 17th century, Johannes Kepler wrote Somnium, which is often regarded as the first real work of science fiction. The book describes a journey to the Moon and how the Earth would look as observed from there. The Man in the Moone, published only 4 years later is also among the first real science fiction works. This book, written by Francis Godwin, as you might guess from the title, describes a journey to the Moon. The author, similarly to many other early pioneers of science fiction, was influenced by the astronomical discoveries of the day, including work by such people as Kepler, Copernicus, Gilbert and others. Despite of such fascination with early science, Godwin’s chosen method of travel to the Moon was huge wild swans, which were connected together in a sort of a kite. Not very scientific, but, hey, let’s give this guy some extra points for creativity.
The 19th century saw a plethora of early science fiction works, the most famous of which were Frankenstein by Mary Shelley, From Earth to the Moon and Journey to the Center of the Earth by Jules Verne and, of course, The Time Machine by H. G. Wells. For us the most important work of these is the mentioned Verne’s story of an incredible journey from Earth to the Moon using a space gun — a cannon that is used to shoot a projectile into space. This projectile could then carry 3 people, including food water, oxygen and other crucial cargo. Verne even included some basic calculations on the requirements for the cannon, which appeared to be surprisingly accurate. As it can be seen from the picture below, the projectile even resembles a modern space shuttle a bit, illustrating how far science fiction has evolved since the beginning of the genre.
Diagram of the interior of Verne's "projectile"
Any Kind Of Vehicle Used To Travel In Space
Now we're getting into an area where it is hard to set any limits on what qualifies as a vehicle, and what kind of travel is relevant. Many - perhaps most - ancient cultures conceived of the motions of the sun and moon as indicating that the respective gods associated with those objects were crossing the sky in enormous, magical boats or chariots of some sort. However, I doubt that many ancient people believed that humans could achieve similar space flight, and the issue of how literally the ancients took these myths is certainly debatable. Still, to some extent, a boat or chariot carrying the sun or moon across the sky might qualify as space travel using a vehicle of some sort.
Ancient depictions of gods carrying the sun across the sky: Above - Ra (Egyptian) in a boat; Below - Helios (Greek) on a chariot.
1The J.J. Astor who wrote "A Journey In Other Worlds" was none other than the famous business tycoon John Jacob Astor. One of the wealthiest people in the world at that time, his family is legendary for being robber barons, creating the Waldorf-Astoria Hotel, and many other well known ventures. J.J. Astor himself achieved a final claim to fame by being the wealthiest person to die aboard the Titanic.
