How did Fawkes get into the Chamber of Secrets?

Question

In Chamber of Secrets, Harry manages to summon Fawkes [due the loyalty to Dumbledore he expresses, not consciously summoning him!] into the chamber of secrets. How exactly did Fawkes get in there?

The way into the chamber had been blocked by the ceiling collapsing when Lockhart's memory charm backfired; when Harry & Ginny & Fawkes return to the blockage, Ron had cleared a sizeable hole in it, but expresses surprise at seeing Fawkes: "Where'd that bird come from?!", implying Fawkes hadn't got into the chamber through the hole Ron had made - he surely would have seen him.

I therefore assume that either Fawkes managed to somehow apparate into the chamber (it's never mentioned that Phoenixes can do this), or found another way in. But if Prof. McGonagall's statement earlier in the book is true, that the school had been thoroughly searched for the chamber (presumably by very powerful wizards, as the time it was opened 50 years before caused the death of a student - you'd have thought they'd have carried out very extensive searches!), and nothing found, we'd have to assume that no other entrance to the chamber existed. (Though if that were true, where did the Basilisk get the food it ate, which we know it ate due to the large number of bones Harry & co walked over when they first got into the chamber?)

Answer 1

Actually, we do see that phoenixes can not only Apparate, but that they, like house-elves, are able to Apparate inside Hogwarts. From chapter 22 of OotP:

"We will need," said Dumbledore very quietly to the bird, "a warning."

There was a flash of fire and the phoenix had gone.

...

There was a flash of flame in the very middle of the office, leaving behind a single golden feather that floated gently to the floor.

"It is Fawkes's warning," said Dumbledore...

Not only that, there's a bit where Fawkes brings Dumbledore with him via Side-Along Apparition. From OotP chapter 27:

Fawkes circled the office and swooped low over him. Dumbledore released Harry, raised his hand, and grasped the phoenix's long golden tail. There was a flash of fire and the pair of them had gone.

Fawkes never takes anyone other than Dumbledore along with him when he Apparates. I assume that's because of the strong bond between the two of them, the same bond that lets Harry summon Fawkes in the first place. Or perhaps phoenixes, despite their ability to lift heavy loads, can't Apparate with more than one other being in tow.

Answer 2

It is mentioned that Fawkes apparated in the Chamber of Secrets in the book, Chapter 17.

Then, as the music reached such a pitch that Harry felt it vibrating inside his own ribs, flames erupted at the top of the nearest pillar. A crimson bird the size of a swan had appeared, piping its weird music to the vaulted ceiling.