Main page of the Phobos section here.
In 1726 Jonathan Swift publishes Gulliver's Travels, which describes the imaginary exploits of Lemuel Gulliver. He learns that the scientists from the Laputa island have...
"...discovered two lesser stars, or satellites, which revolve about Mars; whereof the innermost is distant from the center of the primary planet exactly three of its diameters, and the outermost five; the former revolves in the space of ten hours, and the latter in twenty one and a half; so that the squares of their periodical times are very near in the same proportion with the cubes of their distance from the center of Mars; which evidently shows them to be governed by the same law of gravitation that influences the other heavenly bodies."
Swift's prediction is quite surprising, given the fact that there were no powerful enough telescope to spot the moons at this time:
The 1750 story Micromégas, by Voltaire, which deals with an inhabitant of Sirius visiting our solar system, also mentions the two martians moons, he obviously read Gulliver's Travels.
The Swift story is a starting point for theories in which Phobos would be an 'advanced logistic base' used by aliens on their visit to our planet.
But there is also a less disturbing explanation: Swift knew of the 'celestial harmony' concepts
proposed by Kepler. The idea was that the planets of the solar system must have an
increasing number of satellites progressing as their distance with the sun is.
At the time it was believed that:
Since they could not be seen, maybe he guessed that they had to be very small, and also close to the planet so that they would be lost in its glare. So much for the Jonathan Swift discovery! Unless you wish to check if there is more to it...
Asaph Hall, an astronomer at the Naval Observatory in Washington, D.C. was looking to see if Mars had any moons. He failed to see anything even though he looked over a long series of nights. He was about to give up because he was so discouraged but his wife Angeline Stickey kept encouraging him and suggested he should try one more night. When he discovered the moons he named the crater in her honor because she did not let him give up his dream.
It is sometimes suggested that the reason he named them Phobos (terror) and Deimos (panic) is that he felt so when he remembered Swift's tale, written 150 years earlier.
It is much widely accepted that the name were simply chosen in the Greek mythology, without any special reason except that Phobos was a son of Mars and Venus.