Fawkes left

After Dumbledore died, Fawkes's grief was apparent:
Gulping, Madam Pomfrey pressed her fingers to her mouth, her eyes
wide. Somewhere out in the darkness, a phoenix was singing in a way
Harry had never heard before: a stricken lament of terrible beauty.
And Harry felt, as he had felt about phoenix song before, that the
music was inside him, not without: It was his own grief turned
magically to song that echoed across the grounds and through the
castle windows.
—Harry Potter and the Half-Blood Prince
Later, Harry noticed that Fawkes was done singing his lament, and concluded that he had left.
“Dunno,” said Harry, lying back on his bed fully clothed and staring
blankly upwards. He felt no curiosity at all about R.A.B.: He doubted
that he would ever feel curious again. As he lay there, he became
aware suddenly that the grounds were silent. Fawkes had stopped
singing. And he knew, without knowing how he knew it, that the phoenix
had gone, had left Hogwarts for good, just as Dumbledore had left the
school, had left the world . . . had left Harry.
—Harry Potter and the Half-Blood Prince
However, it is possible that Fawkes left somewhat later. He may have remained for the funeral, although it is ambiguous.
White smoke spiraled into the air and made strange shapes: Harry
thought, for one heart-stopping moment, that he saw a phoenix fly
joyfully into the blue, but next second the fire had vanished. In its
place was a white marble tomb, encasing Dumbledore’s body and the
table on which he had rested.
—Harry Potter and the Half-Blood Prince
Why didn't he stay?
Fawkes has always been associated with Dumbledore. He flew to Dumbledore after saving Harry in the Chamber of Secrets:
Professor Dumbledore was standing by the mantelpiece, beaming, next to
Professor McGonagall, who was taking great, steadying gasps, clutching
her chest. Fawkes went whooshing past Harry’s ear and settled on
Dumbledore’s shoulder, just as Harry found himself and Ron being swept
into Mrs. Weasley’s tight embrace.
—Harry Potter and the Chamber of Secrets
Indeed, as an indication of the strength of the bond between Fawkes and Dumbledore, the latter's Patronus is a phoenix:
Question: What form does Dumbledore’s Patronus take?
JKR: Good question. Can anyone guess? You have had a clue. There was a
little whisper there. It is a phoenix, which is very representative of
Dumbledore for reasons that I am sure you can guess.
Fawkes was called to the Chamber by the strength of Harry's loyalty to Dumbledore.
“First of all, Harry, I want to thank you,” said Dumbledore, eyes
twinkling again. “You must have shown me real loyalty down in the
Chamber. Nothing but that could have called Fawkes to you.” He stroked
the phoenix, which had fluttered down onto his knee.
—Harry Potter and the Chamber of Secrets
This, more than anything else, demonstrates that Fawkes and Dumbledore are in some sense interchangeable. Loyalty to Fawkes is loyalty to Dumbledore, and vice versa. As indicated in this answer, the authorial reason for Fawkes's departure was that "something had to leave the school" when Dumbledore died. It goes beyond that, though: the departure of Fawkes is essentially the departure of Dumbledore.
Fawkes and Dumbledore had had a great deal of time to develop such a connection.
They had most likely been together since before Voldemort purchased his wand:
“Exactly,” said Dumbledore. “Harry’s wand and Voldemort’s wand share
cores. Each of them contains a feather from the tail of the same
phoenix. This phoenix, in fact,” he added, and he pointed at the
scarlet-and-gold bird, perching peacefully on Harry’s knee.
“My wand’s feather came from Fawkes?” Harry said, amazed.
“Yes,” said Dumbledore.
—Harry Potter and the Goblet of Fire
This would have been nearly 60 years (from 1938 to 1998). In many ways, Fawkes was Albus Dumbledore's closest friend. For a phoenix, a generally independent creature, to spend sixty years with a wizard speaks to the depth of their friendship. Fawkes and Dumbledore had decades to build their relationship. Harry had known him for only a tenth of that time, and barely interacted with him.
Fawkes was Dumbledore's friend: not Harry's, not the Order's mascot. He stayed at Hogwarts out of love for Dumbledore.
When his friend died,
Fawkes had no reason to remain.
Note: Image not from Half-Blood Prince