Have the cat be an awakened cat wit Int 18 and maybe some class levels (expert ??) and thus a very high bonus in some int-based skill such as some knowledge or Decipher Scrypt.
The cat doesn't say anything, and always pretends to be a normal cat.
Then when the characters face some enigmatic writing in a deep dungeon and are arguing about which way to go have the cat say, in very polite words something like "excuse me, sirs and madams, I think that you are actually going the wrong way: everybody knows that in that particular ancient drow dialect the word for "left corridor" is different from the modern one, and similar to "right passage". The correct way is passing through that archway and than turn left .... : you can read this in the cronicles of the voyages of Turlin the Old"
After that moment, have the cat usually talk aloud and most of the time saying either philosophical argumentations, quotations from ancient people or generi nonsense like one of the horses in a book from Quenau (sp?).
Or have it behave like the crazy cat in Alice in Wonderland, but only in some circumstances
And, of course, all these effects should be non-dispellable, the cat should not radiate magic.
The idea of the immortal cat is also cool.
(or you could give him the classical 7 lives)