Multi-epoch radial velocity measurements of stars can be used to identify stellar, substellar, and planetary-mass companions. Even a small number of observation epochs can be informative about companions, though there can be multiple qualitatively different orbital solutions that fit the data. We have custom-built a Monte Carlo sampler (The Joker) that delivers reliable (and often highly multimodal) posterior samplings for companion orbital parameters given sparse radial velocity data. Here we use The Joker to perform a search for companions to 96,231 red giant stars observed in the APOGEE survey (DR14) with ≥3 spectroscopic epochs. We select stars with probable companions by making a cut on our posterior belief about the amplitude of the variation in stellar radial velocity induced by the orbit. We provide (1) a catalog of 320 companions for which the stellar companion’s properties can be confidently determined, (2) a catalog of 4898 stars that likely have companions, but would require more observations to uniquely determine the orbital properties, and (3) posterior samplings for the full orbital parameters for all stars in the parent sample. We show the characteristics of systems with confidently determined companion properties and highlight interesting systems with candidate compact object companions.