Here's one reducing the redundancy in the strings:

$s="string";$m="monkey";print "Please enter the $s to be searched for 
+the $s '$m':\n";print "\u$s '$m' was ",<>!~/$m/&&'not ',"found in the
+ input $s.\n";
[download]

154 characters (but no perl shebang -- is that required for the golf stroke count?)

Update:170 with the shebang.