Every second, at least one human on this planet is standing before a sign on a door or a pair of doors, and thinking: "which is the men's (women's) room?"
Here are ways in which they are helped to decide...
COITAL METAPHORS rely on mapping imagery of the physical act of sex onto a pair of target shapes. can sometimes be unclear, as in the following instance (labels mine).

[source]
This is the only instance of this type of designation I could find, so it's possible I'm over-generalising...
GENITAL SHAPES depict male & female genitalia, in varying degrees of exactness

[source]
_3.jpg)
[source]
BODY SHAPES foreground the shapes of body parts specific to gender
[source]
COMPARATIVE URINATION depict differences in how different genders urinate
[source]
[source]
variations also depict the experience of waiting, something that probably generates empathy universally...
[source]
GENDER TRANSFERENCE from animals to humans

[source]
[source]
REFERENCE BY MATERIAL POSSESSION identifies gender by things typically owned
[source]
[source]
DIRECT PORTRAYAL depict a pair of clear, if unknown, instances of each sex
[source] Update: a reader informs me that these are "Basque icons of Amuma and Eichicha (gramma and grampa). Every Basque home has them."
[source]
CULTURALLY SPECIFIC REFERENCES images that are well-known within the host culture, and hence recognised easily
[source]
[source]
some of these clearly require emic knowledge... I had difficulty understanding this pair of signs:
[source]
this category also covers these symbols (if only because they are predominantly western):
[source]
with modifications, although given that this next one is from colonial williamsburg, it's anybody's guess whether this is an emic depiction or one designed for visiting tourists:
[source]
ARBITRARY/CONVENTIONAL SYMBOLISM pictorial signifiers of gender
[source]
these are culturally specific as well, of course.
Now, this is not a mutually exclusive or completely exhaustive set, but there's enough variation in here to be interesting. There are variations on these themes, such as hyper-gendering (also this), and satire, and even those that set up (and resolve) a conflict of meaning.
Usually, the act of urination in public is unremarkable, even though performing it incorrectly has social costs - embarrassment, one fails to make the correct identification and walks into the women's instead of the men's room, or stigma if one is not able to control one's bladder till the appropriate sanctum is reached. Nevertheless, or maybe precisely because of this, this act is rich with meaning, as the above examples show, and there's enough opportunity for adding delight to that moment of decision. Further, just as the viewer is delighted - and sometimes challenged with uncovering the meaning - another kind of meaning is being made: the viewer is being told something about the institution that houses the signage. Some impression is being given off, an identity is being performed: "this is how cool we are" says the sign. The viewer walks away with this unique memory of the institution (note that a lot of these signs are in bars or pubs), and their experience of it becomes just a little more textured. This is branding and marketing at its finest: so thoroughly integrated into the experience that it becomes invisible.
with thanks to mara codalli for her 'ladies & gentlemen' photoset on flickr, the toilet signs project, and "Coolest Toilet Signs Around The World" by damn cool pics.