‘It’s a shame you had to see him on a Burning Day,’ said Dumbledore, seating himself behind his desk. ‘He’s really very handsome most of the time: wonderful red and gold plumage.
Fascinating creatures, phoenixes. They can carry immensely heavy loads, their tears have healing powers and they make highly faithful pets.’
Chamber of Secrets - page 155 - Bloomsbury - chapter 12, The Polyjuice Potion
Dictionary.com offers the following as definitions for faithful: steady in allegiance or affection; loyal; constant: faithful friends.
As Gorchestopher H mentioned, Fawkes apparently knew who Dumbledore was each time he burned and regenerated. In the above passage I quoted from Chamber of Secrets, J.K. Rowling put the emphasis on "faithful", not me. In order for Fawkes to exhibit characteristics like steadiness in allegiance or affection, loyalty, and constancy, I think Fawkes would have to retain his memory with each regeneration.