What a coincidence. I made good use of this module today because I needed to have bolded text in my menu items:
After enabling you'll get a checkbox on each menu item that allows you to add HTML to the menu title (anything inside the anchor essentially). So this is where you would put your
<img> tag or the markup necessary for your icons.
Note for security, make sure only trusted users have the ability to use this option, as you can imagine it creates an opportunity to embed malicious code.
EDIT: OP asked how you might add icons using this technique. I would use an icon font. For example with Font Awesome you can put in some markup like
<i class="fa fa-refresh"></i> and it will use CSS to display the icon there. Font Awesome covers most bases. If you can't find something specific try icoMoon or Fontastic.
It's really up to you how you implement this. See the other poster's answer for a pure CSS solution.