You can associate an icon with any menu. The easiest way to do this might be to just use a regular MenuItem and set its icon to either a checked or unchecked checkbox whenever it is clicked. You might put that logic in a subclass of JMenu and use that class.
http://docs.oracle.com/javase/tutorial/uiswing/components/menu.html