A handful of effects that readers might assume are undetectable are explicit that victims recognize them. For example, a creature knows that it can't cast defensively when it's threatened by a foe that possesses the feat Mage Slayer (Monster Manual V 85), and a creature knows that its slightest movement provokes an attack of opportunity from a foe that threatens it and that's in the Devoted Spirit martial stance thicket of blades (Tome of Battle 61). However, the vast majority (and, no, not a small majority) of effects just don't say one way or the other whether an affected creature is aware of them or not (q.v. suggestion, this related Pathfinder question that reverberates from 3.5). Such is the case here: The text details at length what happens to the spellthief when she steals a spell, but it seems to care little about the unfortunate victim.
In short, there's no direction from the text on whether or not the victim knows a spell's been stolen or what spell's been stolen. The DM makes that decision.
This DM would rule that a creature knows if its spell is unavailable
This DM prefers to hew closely to the rules, so when an effect is not described as having an obvious effect, he tends to rule that the effect does not have an obvious effect. That means, for example, spells that seem on the page flashy—perfect for awing pathetic noncasters!—sometimes in this DM's capaigns just aren't. (Yes, I make this clear to my players early on.)
On the other hand, this DM is also a big fan of player agency, speeding play, and friendship. Telling a player that his PC has wasted his time because neither knew that the PC's special abilities had fundamentally changed sounds like a recipe for destroying all three.
That is, it's one thing to tell the player that his sorcerer PC loses the use of his disintegrate spell after the weasely little NPC spellthief jammed a shiv into his sorcerer's gut, and I think it's totally okay not to tell the player that she was a spellthief, and I think that it's also okay not to to tell the player that his sorcerer will get the disintegrate spell back in a minute. (This DM sees such concerns as healthy stress.) But not telling the player that his PC's lost the use of the disintegrate spell then letting the player have his PC go through the motions of casting the gone spell only to see it fail? That's a bridge too far.
This DM can imagine a player having some pretty harsh words for him were he to do that. I mean, not only has every standard action grown exponentially in importance during the course of twelve levels of play (the minimum level a sorcerer needs to be to cast the spell disintegrate), but also the concept of knowing instinctively what spells a caster has available is so fundamental to the character—so bound up with the idea of being a caster—that removing even part of a caster's casting ability secretly—without informing the player—seems, to this DM, like a violation.
So while the rules very well may tacitly—with their silence on the subject—support the DM secretly tracking which spells an NPC spellthief has stolen from the PCs and letting the PCs waste actions trying to cast them, this DM doesn't imagine that being fun for anyone: It's more work for the DM, and it'll make your players angry.
And, therefore, by the same token, an NPC that sees his spell stolen by a PC spellthief should likewise be informed of the loss. The PC spellthief may be initially disappointed at the ruling, but perhaps a mile in another's moccasins will help the player see the wisdom in it. And, if it doesn't, a couple of encounters with NPC spellthieves almost certainly will.
(Arguably, the closest thing to a spellthief's steal spells ability's effect is the supernatural ability energy drain that sees a victim that casts spells lose access to one spell of the highest level as if it had been cast. This, in this DM's opinion, is obvious the caster because it's as though the spell's been cast. This reader imagines the caster's HUD flashing Energy Drain! followed by the caster's disintegrate spell disappearing from her mental list of prepared spells. This is, though, different enough from the spellthief's steal spells ability that this DM wouldn't use it as a precedent, but another DM might.)