Since I was not aware this was a duplicate, I would suggest reading Slytherincess' answer as it supports both the first and the second guess. I think, that one of the most interesting part is about Fawkes being able not just withstand a hit by Avada Kedavra, but to actually swallow it, shame I did not recall this occasion.
Fawkes closed his eyes
I did not really find a satisfying canon proof, so I will make some more or less wild guesses. Firstly let us recall the situation:
Fawkes was soaring around its head, and the basilisk was snapping
furiously at him with fangs
From this we can see, that Fawkes did not really sneak up on the Basilisk from behind (reaction of @ash_k29 comment), it looks like Fawkes really had to be careful not to be hit by the fangs. For this part I think he would need to have open eyes, so this theory is unstable.
long and thin as sabers — Fawkes dived.
However during the dive I think he could take his chance (can't think of the better English idiom), I made this assumption from the following:
His long golden beak sank out of sight and a sudden shower of dark
blood spattered the floor. The snake’s tail thrashed, narrowly missing
Harry, and before Harry could shut his eyes, it turned — Harry looked
straight into its face and saw that its eyes, both its great, bulbous
yellow eyes, had been punctured by the phoenix; blood was streaming to the floor, and
the snake was spitting in agony.
It was satisfactory to only puncture the eyes, I can imagine him landing on Basilisk head and trying to slash its eyes, and for that he would not necessarily need to see (if he landed correctly)
Fawkes as a magical creature
The next possibility is, that Fawkes could not be hurt by Basilisk stare because as being powerful magical creature, he would be safe. From FBaWTFT:
Phoenix song is magical; it is reputed to increase the courage of the
pure of heart and to strike fear into the hearts of the impure.
Phoenix tears have powerful healing properties.
Of course, this does not says anything about ability to surviving the Basilisk stare, but: being a wizard biologist is pretty hard (look at Hagrid, or Professor Sprout & Grubbly-Plank), I assume any information from the book would need some kind of experiment. So, try to imagine setting up the experiment to test whether Phoenix can withstand the Basilisk stare, without any unfortunate accidents (although I would suggest setting the experiment in the bathroom).
Fawkes a bird
The last of my guesses is quite dumb. Thanks to petrified Hermione we get this information:
Spiders flee before the Basilisk, for it is their mortal enemy, and
the Basilisk flees only from the crowing of the rooster, which is
fatal to it.
So, aside from that Basilisk probably do not search for properties in the countryside, this says, that as Fawkes is a male bird might be the advantage for him to be immune (I know, this sounds a bit too wild, as I promised). Funny think would be if Dumbledore sent Harry a rooster.
But what is true, that being mortal enemy to some creature does not necessary mean to be bigger and stronger (mortal enemy in the sense of being the thing you can hardly hurt with the best you got, like the stare).