We use an icon with 3 horizontal lines. Icon for easy has only the lowest line, medium - lowest and middle lines, hard - all lines. For more info check: http://itunes.apple.com/us/app/neuroshima-hex/id391297152?mt=8
Call of Duty uses a mugshot of a person looking more bad___ and war-torn for each higher difficulty, with a skull and crossbones for veteran.
What type / genre of game are you thinking of? Creating something suitable will also depend on the look of your menu selection screen as the obvious choice could simply be a name list [Childs play / normal / tough / nightmare] or a simple icon colour change from yellow, green, orange, red to signify four levels of difficulty. Fire up some more info and I am sure the TA posse will provide some great feedback for you.
I just went skiing today and thought of: Not everybody would immediately recognize the symbols but I think it would be pretty self explanatory. Or else maybe just one star, two stars, and three stars.
They're are definitely certain options that would work for certain genres. If it's a game with characters (as opposed to a game made of abstract objects or primitives) maybe have a picture of the enemy to represent the difficulty. Example: If there's a werewolf bad guy show: Easy - little puppy Medium - Normal werewolf Hard - Bigger ferocious looking weremonster with giant teeth and red eyes. I like this idea and I wish I wasn't so lazy. Then I'd give off my butt, fire up maya (like I went to school for) and get back into lower poly modeling.