Assuming a hitherto unknown microbe is found - who gives it its name?
I sthere any reason for your question to be specific to microbes? Whether a microbe or multi-cellular organism is found, the problem is the same. Who name it?
Who name it?
Whoever discovered it. Of course, discovering a new species is not as easy as just taking a picture. One has to provide a very thorough description of the species morphology and eventually argue that it should be considered as a new species and not just as a subspecies or something else. See here for discussion on the definition of a species.
How does the discoverer name it?
If the new species is considered part of an already existing genus, then the author has to keep the genus name. The species name the author chooses is mainly to up himself / herself. Consider for example Macrocarpaea dies-viridis (dies-viridis means "green day") was named like this because the researchers were listening to Greenday when they found it!
The person who discovers it. Or, maybe more precisely, the person who tells other people that they discovered it.
Journals and societies may have restrictions or guidelines on how those names are chosen, which certainly has some practical implications for the naming. Here is one example from the Journal of Clinical Microbiology:
For guidelines regarding new names and descriptions of new genera and species, see the articles by Tindall (Int J Syst Bacteriol 49:1309-1312, 1999) and Stackebrandt et al. (Int J Syst Evol Microbiol 52:1043-1047, 2002). To validate new names and/or combinations, authors must submit three copies of their published article to the International Journal of Systematic and Evolutionary Microbiology.
It is recommended that a strain be deposited in at least two recognized culture collections in different countries when that strain is necessary for the description of a new taxon (Int J Syst Evol Microbiol 50:2239-2244, 2000).
Since the classification of fungi is not complete, it is the responsibility of the author to determine the accepted binomial for a given organism. Sources for these names include The Yeasts: a Taxonomic Study, 5th ed. (C. P. Kurtzman , J. W. Fell, and T. Boekhout, ed., Elsevier Science, Amsterdam, Netherlands, 2011), and Dictionary of the Fungi, 10th ed. (P. M. Kirk, P. F. Cannon, D. W. Minter, and J. A. Stalpers, ed., CABI International, Wallingford, Oxfordshire, United Kingdom, 2008); see also http://www.speciesfungorum.org/Names/Fundic.asp.
Names used for viruses should be those approved by the International Committee on Taxonomy of Viruses (ICTV) and reported on the ICTV Virus Taxonomy website. In addition, the recommendations of the ICTV regarding the use of species names should generally be followed: when the entire species is discussed as a taxonomic entity, the species name, as with other taxa, is italic and has the first letter and any proper nouns capitalized (e.g., Tobacco mosaic virus, Murray Valley encephalitis virus). When the behavior or manipulation of individual viruses is discussed, the vernacular (e.g., tobacco mosaic virus, Murray Valley encephalitis virus) should be used. If desired, synonyms may be added parenthetically when the name is first mentioned. Approved generic (or group) and family names may also be used.
Microorganisms, viruses, and plasmids should be given designations consisting of letters and serial numbers. It is generally advisable to include a worker's initials or a descriptive symbol of locale or laboratory, etc., in the designation. Each new strain, mutant, isolate, or derivative should be given a new (serial) designation. This designation should be distinct from those of the genotype and phenotype, and italicized genotypic and phenotypic symbols should not be included. Plasmids are named with a lowercase "p" followed by the designation in uppercase letters and numbers. To avoid the use of the same designation as that of a widely used strain or plasmid, check the designation against a publication database such as Medline.