With the IRAM 30 m telescope we observed HCN(1 --> 0) emission from five ultraluminous galaxies, three lower luminosity interacting systems, and two gas-rich normal galaxies. There are huge masses of high-density gas (2 x 10(10) M.) in the ultraluminous galaxies, which shows star formation, rather than active galactic nuclei, generates their infrared luminosity. HCN traces H-2 at a much higher density, approximately 10(4) cm-3, than CO (approximately 500 cm-3). The ultraluminous galaxies Mrk 231, Arp 193, Arp 220, and NGC 6240 have HCN(1 --> 0) luminosities greater than the CO(1 --> 0) luminosity of the Milky Way. Mrk 231 has 3 x 10(10) M. of H-2 at a density near 10(4) cm-3, approximately 300 times the mass of dense H-2 in the Milky Way. We also detected HCO+(1 --> 0) emission from Mrk 231 and Arp 220 at half the strength of HCN(1 --> 0). The ratio of HCN to CO luminosity is 1/6 for ultraluminous galaxies, but only 1/80 in normal spiral galaxies. A large fraction of the molecular gas in ultraluminous galaxies, perhaps 50%, is in very dense regions similar to star-forming cloud cores, rather than in the envelopes of giant molecular clouds. The ratio of far infrared to HCN luminosity is similar in both ultraluminous galaxies and normal spirals, including the Milky Way, which suggests the star formation rate per mass of dense gas is independent of the infrared luminosity or the state of interaction. The molecular gas density in the central regions of the ultraluminous galaxies, approximately 500 M., pc-3, is similar to the stellar density in the centers of elliptical galaxies, consistent with the idea some mergers may eventually become ellipticals.