Over at the Oxford University Press blog, Michael Quinion, author of Gallimaufry: A Hodgepodge of Our Vanishing Vocabulary, suggests that it might be impossible for humans and aliens ever to communicate. He writes:
The alien and the human would be facing much intensive co-operative work to get a basic understanding of each other's methods of communication, language and culture. Ask any field linguist who has encountered a previously unknown tribe just how difficult this can be, even when both parties are human. SF writers struggle with this problem every time they write a first-contact story.
However, few SF writers are linguists, matched only in lack of expertise by their readers. The solutions can seem to owe as much to the black arts as to science (but then, as Arthur C Clarke said, "any sufficiently advanced science is indistinguishable from magic"). One solution, common enough to be a convention of the genre, like hyperspace, is the universal translator. The Star Trek series found it an invaluable time-saver, though a version of it appeared first in Murray Leinster's story First Contact of 1945.
Even if it translates the words, it may not get the message across. Naomi Mitchison suggested in Memoirs of a Spacewoman (1962) that trying to communicate with a five-armed starfish would show the extent to which our bilateral symmetry constrains us to a binary view of the world - true versus false, right versus wrong, black versus white. In The Mote in God's Eye (1974), Larry Niven and Jerry Pournelle imagine three-armed aliens, who argue not just "on the one hand" and "on the other hand", but also "on the gripping hand", a trilateral logic. C J Cherryh's Hunter of Worlds (1977) presents the language of the Iduve, in which there's "no clear distinction between noun and verb, between solid and action", so that translation cannot be literal if it is to be meaningful. Jean-Luc Picard comes across something similar in Star Trek: The Next Generation when he encounters a race that speaks only in metaphor.