Certainly "they" is an option, and often recommended for this; but "he or she", and picking one at random and alternating, are also both accepted and commonly used: http://www.unc.edu/depts/wcweb/handouts/gender.html
They all have their advantages and disadvantages, but I was more struck at the suggestion that using "she" was illegitimate, when in actual usage it plainly isn't.