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?)