We have performed a search for radiative b-hadron decays using events produced in p (p) over bar collisions at roots=1.8 TeV and collected by the Collider Detector at Fermilab. The decays we considered were (B) over bar (0)(d)-->(K) over bar*(0)(-->K(-)pi(+))gamma, (B) over bar (0)(s)-->phi(-->K+K-)gamma, Lambda(b)(0)-->Lambda(-->ppi(-))gamma, and their charge conjugates. Two independent methods to identify photons from such decays were employed. In the first method, the photon was detected in the electromagnetic calorimeter. In the second method, the photon was identified by an electron-positron pair produced through the external photon conversion before the tracking detector volume. By combining the two methods we obtain upper limits on the branching fractions for the (B) over bar (0)(d), (B) over bar (0)(s), and Lambda(b)(0) radiative decays which, at the 95% confidence level, are found to be B((B) over bar (0)(d)-->(K) over bar*(0)gamma)<1.4x10(-4), B((B) over bar (0)(s)-->phigamma)<1.6x10(-4), and B(Lambda(0)(b)-->Lambdagamma)<1.9x10(-3).