Comment 37 for bug 432876

There are basically two ways of fixing this bug.
1) As stated before, under System -> Preferences -> Appearance check "Show icons in menus". After restarting Firefox, the icons should be there again.
2) If you don't want the icons in other applications, and you feel they are missing only in Firefox search bar, install the Stylish extension [1] and add the following as a new style:

 #search-popupset .menu-iconic-left {
     visibility: visible!important;
 }

note: remove "#search-popupset" if you want the icons in all Firefox menus.

I believe this is a bug in Firefox, which should be reported upstream. Firefox should display these icons even if "Show icons in menus" is unchecked. I opened it: https://bugzilla.mozilla.org/show_bug.cgi?id=525714

[1] https://addons.mozilla.org/fr/firefox/addon/2108