There's a study of handedness in baboon communicative gestures by Meguerditchian and Vauclair. Discovery News has a report about it (via Palanthsci). From the report, you wouldn't realize that these gestures themselves have been known from field studies for forty years. The new part is the evidence for lateralization, which is given as evidence for an ancient role of gestures in communication:
Since the right hand is controlled by the brains left hemisphere, which is the source of most linguistic functions, scientists believe communication by hand likely existed in apes 30 million years ago and was a forerunner to spoken and written language among people.
The last few paragraphs of the paper by Meguerditchian and Vauclair have several points to make in relation to communication and gesture. Here's the last, with the summary:
From a comparative viewpoint, regarding our results and the literature, we suggest the existence of a continuity between asymmetries of speech related gestures and asymmetries of communicative gestures in chimpanzees and now in baboons, even though the degree of population-level right-handedness is lower in non-human primates than in humans. From an evolutionary viewpoint, we suggest that the neuroanatomical substrate of manual communication controlled by the left cerebral hemisphere may have existed in their common ancestor at least 30 million years ago and may be considered as the precursor of the human language area. Our results hence bring additional support to the view that lateralization for language in humans may have evolved from a gestural system of communication lateralized in the left hemisphere (Meguerditchian and Vauclair 2006:173).
The right-handedness angle is, to me at least, much less interesting than the communication aspect. But the two are interrelated, as is made clear by the penultimate paragraph:
We thus suggest that the communicative functions of the hand could imply a different cerebral substrate than that involved in their manipulative functions: a communicatory left-hemisphere system may be involved for the production of gestures. This system would more strongly favor the use of the right hand than bimanual coordinations for object manipulations. Moreover, results from recent studies in chimpanzees that used RMI (magnetic resonance imaging) to investigate the neurobiological basis of handedness are convergent with this argument. In effect, it was found that asymmetries of homologous language areas did not correlate with handedness for non-communicative motor actions , but a significant correlation was shown between asymmetries in Brodmann's area 44 (homologous of Broca's area) and hand preferences for communicative gestures  (ibid.).
The idea is that brain lateralization for communication initiated hand preferences for communicative functions; these remain separate from manupulative functions in most anthropoids and therefore communicative functions are more highly lateralized.
On the other hand, given recent evidence that Broca's area and its right homologue are involved in all kinds of temporally sequenced hierarchical actions. It may be that communicative actions fit that category more often than manipulative actions for nonhuman primates.
If so, it would be of great interest to see whether complex, temporally sequenced manipulative actions -- like maybe extractive foraging -- require hierarchical temporal organization more than most other kinds of activities. Maybe there are logical connections between food extractive actions that require hierarchicalization and communicative actions. Maybe the anthropoid style of communication has emerged in part from brain functions developed originally for complex motor sequences.
Well, that's a lot of "maybes", and other scenarios could take form instead. For instance, most anthropoid communications themselves aren't very "hierarchical". The baboon hand gestures are not especially long or complex, nor are most vocalizations.
What kinds of communications are hierarchical? Some threat displays are fairly long and complex, and they also may use both vocal and visual channels. These characteristics have a communicative purpose: by emphasizing the threat message through long agonistic rituals and multichannel redundancy, the sender advertises sincerity. A threat that is perceived as insincere or unserious may be worse than no threat at all.
But there is another element to this: threat displays are long and complex in themselves because they are minimally interactive. They represent circumstances under which individuals wish to convey a clear message without interference or feedback. They are multichannel and long in part to dominate the bandwidth available for communications within the group. In other words, they demand attention because they impede other communications and interactions.
This points to a way that communication is always hierarchical -- it generally involves feedback. The sender is interested in whether other individuals receive the message, and may alter his or her further behaviors as a result. This may mean resending a message if there is no sign of its receipt; it may mean some other course of action depending on the signs emitted by the receivers.
That's the kind of context-dependent sequencing indicated by the Broca's area research I cited earlier. And it also would seem like the kind of context-dependent sequencing used for learning and executing complex manipulative sequences, like tool manufacture and use.
Meguerditchian A, Vauclair J. 2006. Baboons communicate with their right hand. Behav Brain Res 171:170-174. DOI link