For existing addons you'll have to find its code and change the code where operators are added to menus.
When you write your own add-on, you can choose a different icon by specifying the icon parameter to the operator function with which you register your operator in a function.
From the Mesh Add operator template in the Blender text editor the snippet:
def menu_func(self, context):
For a list of icons to choose from see the blender documention. There are many places where you can define an icon, but there is only one list. For instance for the menu function of a layout. It takes an icon, the list is the same.
Icons outside these are not (yet) supported. You can replace the entire icon set though by specifying an icon file at the bottom of the User Interface section of the theme editing in User Preferences