I think "entitled to every man's evidence" means that there is a compulsory subpoena power to make people testify. One can call a hostile witness, and in the absence of a corresponding privilege against testifying, the witness can be punished for refusing to testify, as a contemnor (or for testifying falsely, as a perjuror).

This idea is distinct from search and covert eavesdropping powers, which may have also existed at common law but perhaps not under that same principle?