It's well established that Harry's parents, Lily and James Potter, had doe and stag Patronuses respectively. It's also well established that falling in love can change a person's Patronus; for example Tonks' werewolf and Snape's doe. There's also this quote:
Chely: James patronus is a stag and lilys a doe is that a coincidence?
J.K. Rowling: No, the Patronus often mutates to take the image of the love of one's life (because they so often become the 'happy thought' that generates a Patronus).
30 July 2007 Bloomsbury live chat with J.K. Rowling
which suggests that this latter point is true for the Potters.
Given that James' Animagus form was a stag, and that his Patronus was obviously affected by that, the conclusion is that Lily's Patronus is a doe because she fell in love with him.
Is there any canon evidence that says what form Lily's Patronus took prior to her falling in love with James? Failing that, I'd also consider canon proof that Lily never cast the Patronus charm before she fell in love with James as satisfactory evidence that her Patronus was "always" a doe.