>perl -wMstrict -le
"print '------ output ------';
 my $s = shift;
 print $s;
 my @chunks = split / AND /, $s;
 @chunks = map { /OR/ ? qq{($_)} : $_ } @chunks;
 print join ' AND ', @chunks;
"
"huckabee AND jfkadlsfj fdsfldfj06329 OR reagan AND OReilly AND clinto
+n OR sebelius OR mccain"
------ output ------
huckabee AND jfkadlsfj fdsfldfj06329 OR reagan AND OReilly AND clinton
+ OR sebelius OR mccain
huckabee AND (jfkadlsfj fdsfldfj06329 OR reagan) AND (OReilly) AND (cl
+inton OR sebelius OR mccain)
[download]

(Note the  '... AND (OReilly) AND ...' mis-conversion.)
(Sorry for the line wrap!)

A slight improvement that avoids confusion with embedded  'OR' substrings (also is tolerant of variable whitespace around the  'AND' connective, putting back just what it finds):

>perl -wMstrict -le
"print '------ output ------';
 my $s = shift;
 print $s;
 my @chunks = split m{ (\s+ AND \s+) }xms, $s;
 @chunks = map { m{ \b OR \b }xms ? qq{($_)} : $_ } @chunks;
 print join '', @chunks;
"
"huckabee AND jfkadlsfj fdsfldfj06329 OR reagan AND OReilly  AND   cli
+nton OR sebelius OR mccain"
------ output ------
huckabee AND jfkadlsfj fdsfldfj06329 OR reagan AND OReilly  AND   clin
+ton OR sebelius OR mccain
huckabee AND (jfkadlsfj fdsfldfj06329 OR reagan) AND OReilly  AND   (c
+linton OR sebelius OR mccain)
[download]