I would suggest at least initially offering a variety of pillows. Different people have different pillow preferences based on how they sleep; a back sleeper wants a firmer, thinner pillow, a side sleeper wants a firmer, thicker pillow, and a front sleeper wants a softer, middle-thickness pillow, most commonly, but even there you see a huge range.
As a toddler probably doesn't yet have a good idea of what sort of pillow she/he will prefer over the long term (and I'm sure it will change several times over the years), the best thing to do is to let her/him figure it out by trial and error.
For my three year old, he has two or three pillows to choose from; a smallish Thomas shaped pillow that's pretty thick, a homemade pillow from sewing class that's thinner but wider, and sometimes a third very large thick pillow.
As far as materials go, I imagine it depends on allergies (ie, if you need a 'hypoallergenic' pillow; my feeling is those don't do much, but your mileage may vary), but otherwise you should just go with whatever feels best to her. I wouldn't buy anything terribly expensive at first, at least until she figures out what she likes.