Understanding the physical processes that drive star formation is a key challenge for galaxy formation models. In this article we study the tight correlation between the star formation rate (SFR) and stellar mass of galaxies at a given redshift, how halo growth influences star formation, and star formation histories of individual galaxies. We study these topics using Illustris, a state-of-the-art cosmological hydrodynamical simulation of galaxy formation. Illustris reproduces the observed relation (the star formation main sequence; SFMS) between SFR and stellar mass at redshifts z=0 and z=4, but at intermediate redshifts of z~2, the simulated SFMS has a significantly lower normalisation than reported by observations. The scatter in the relation is consistent with the observed scatter. However, the fraction of outliers above the SFR-stellar mass relation in Illustris is less than that observed. Galaxies with halo masses of ~10^{12} solar masses dominate the SFR density of the Universe, in agreement with the results of abundance matching. Furthermore, more-massive galaxies tend to form the bulk of their stars at high redshift, which indicates that `downsizing' occurs in Illustris. We also studied the star formation histories of individual galaxies, including the use of a principal component analysis decomposition. We find that for fixed stellar mass, galaxies that form earlier have more-massive black holes at z=0, indicating that star formation and black hole growth are tightly linked processes in Illustris. While many of the properties of normal star-forming galaxies are well-reproduced in the Illustris simulation, forming a realistic population of starbursts will likely require higher resolution and probably a more sophisticated treatment of star formation and feedback from stars and black holes. ; Comment: 16 pages, 16 figures, Accepted for MNRAS, Section 6 and Figure 16 are new. Data is available at http://martinsparre.com/dataproducts