We report results from a search for neutral Higgs bosons produced in association with b quarks using data recorded by the D0 experiment at the Fermilab Tevatron Collider and corresponding to an integrated luminosity of 7.3 fb{sup -1}. This production mode can be enhanced in several extensions of the standard model (SM) such as in its minimal supersymmetric extension (MSSM) at high tan{beta}. We search for Higgs bosons decaying to tau pairs with one tau decaying to a muon and neutrinos and the other to hadrons. The data are found to be consistent with SM expectations, and we set upper limits on the cross section times branching ratio in the Higgs boson mass range from 90 to 320 GeV/c{sup 2}. We interpret our result in the MSSM parameter space, excluding tan{beta} values down to 25 for Higgs boson masses below 170 GeV/c{sup 2}.