Crookshanks is half-Kneazle and quite intelligent as a result.
On a page from her old website, JK Rowling described Crookshanks as “unusually intelligent”, and confirmed long-held fan suspicions that Crookshanks wasn’t just a cat:
When I decided to give Hermione an unusually intelligent cat I gave him the appearance of this haughty animal, with the slightly unfair addition of bandy legs.
Crookshanks, as anybody who has read Fantastic Beasts and Where to Find Them will have guessed, is half Kneazle.
The entry for Kneazle in Fantastic Beasts includes a reference to their intelligence, and the sentence I’ve highlighted was the basis of theories of his hybrid nature:
A small, cat-like creature with flecked, speckled, or spotted fur, outsize ears, and a tail like a lion’s, the Kneazle is intelligent, independent and occasionally aggressive, though if it takes a liking to a witch or wizard, it makes an excellent pet. The Kneazle has an uncanny ability to detect unsavoury or suspicious characters and can be relied upon to guide its owner safely home if they are lost.
The exact details – why are Kneazles such good dark detectors – isn’t addressed in canon; we’re just told that they are, and no more.