A naming language is a conlang (or invented language) that is meant to be just complex enough to appear like a real language but in fact is missing a few major key features, like a functional grammar and complete vocabulary.
Such a language is useful for stories because the author does not need to spend years inventing a full conlang, but can instead focus hir energies on the actual story.
A naming language gets its name from the fact that it is most commonly used simply to name characters and objects in a story. One example of this is in Watership Down, the language they speak is Lapine, but it does not have a functional grammar and only a short vocabulary. At the same time, however, it is perfectly enough to use for naming some of the characters and objects in the world. (for example, silflay, to eat outside)
Most of the time, if the characters in the book have to speak a language, the author simply uses grammar heavily based off of a language of Earth, i.e. German or French. This, combined with a small vocabulary of only about two hundred words, one can make fully convincing dialog, at least to an unexperienced linguist.
Some examples of naming languages include Verdurian (zompist.com), Lapine, and (sort of) Al Bhed (although it is actually a code).
At the aforementioned zompist.com, there is an excellent guide to creating a naming language. Another place to look is langmaker.com, which not only has more information, but a program to help one make hir own language (Windows only).