It could be similar to the search for extraterrestrial life... Anything like a Star Trek rubber-foreheaded alien would be obvious, but very unlikely, and presumably even if you found that they do/have existed these individuals would be just as much one branch of a tree of life as we are, meaning many more phenotypes (down to a whole mass of single-cell microbes) exist[1] that might not be quite so recognisable at first glance, just from some snapshots, if your initial view isn't fortunate enough to include anything not mistakable with xenogeological features/etc.
Start delving, perhaps looking for more subtle cues in an otherwise lifeless-looking scenario, and perhaps something akin to (R/D)NA is probably what we'd see if we're talking chemical-based life[2], packaged into cells (if we get a working 'soup', rather than merely the fossilised and desicated remains of whatever there was) but that's an assumption we may have to overturn once we aren't so observationally insular on this matter. We can't even assume the basic chemicals involved, down even to the carbon-backbone. Although for sure(?) more likely going to be carbon-based in any place we're going to concentrate our searches, as we're probably not going to look so much in places where silicon/whatever is the more apt core element.
At least we do have a slightly more diverse experience of intelligence. The effective hive-minds of insect colonies give some clues of what differences we might expect, or the more distributed brains of various cephalalods (undeniably intelligent) or perhaps even a 'mind' of sorts by the being that is a Wood-Wide Web at the other end. And if that's indeed one dimension to 'psychotype', maybe there are more than just merely how centralised/distributed the 'thinking' is.
But even by that measure alone, don't expect an AI/'personality' to reside upon a single handy ejectable chip, such as a T-800, or even on a set of handy cartridges, like with HAL9000. It may be confined to a black box with handy keyboard to chat to it through, at least by design, but even then you would be hard pressed to be able to point to a single seat of 'intelligence' (the whole HDD, if there is just the one, is not allowed; nor the whole processor/an entire core). And if it truly is emergent, as our own intelligence/sentience/sapience/environmental-reactivity has done from our own biochemical assemblage, then the graspable identification of what is intelligent might be a matter of casuistry. i.e. "I'll know it when I see it", but only once it gets past an arbitrary threshold of vague and blurry maybeness.
[1] Probably less visible if they are coming to see us, unless it's with a balanced "ark" or biodome-equipped spaceship, but there home planets (or long-term colonised ones) would have xenobacterial clusters and slimes aplenty even if they've done a fairly good job to hide themselves and their "pets" away from prying eyes, or had their extant civilisation and all its trappings killed off by whatever unfortunate process.
[2] As opposed to magneto-plasmic or something even more ascended/trancended beyond our more narrow experiences.