$hashOfStuff{$key}{$newThing} = undef #That the key exists is sufficient
if (exists $hashOfStuff{$key}{$testThing})
{
    ...
}