Rather than moritz's approach of Re: Building a boolean search engine, my preference would be for a more 'factored' regex. While more verbose, it is also, IMHO, more comprehensible, flexible and maintainable. YPMV.

>perl -wMstrict -le
"my $and = qr{ \b AND \b }xms;
 my $or  = qr{ \b OR  \b }xms;
 my $not_connective = qr{ (?! $and | $or) }xms;
 my $term  = qr{ \b (?: $not_connective \w)+ \b }xms;
 my $terms = qr{ $term (?: \s+ $term)* }xms;
 my $or_terms = qr{ $terms (?: \s+ $or \s+ $terms)+ }xms;
 print '------ output ------';
 my $s = shift;
 $s =~ s{ ($or_terms) }{($1)}xmsg;
 print $s;
"
"huckabee AND jfkadlsfj fdsfldfj06329 OR reagan AND OReilly   AND  cli
+nton OR sebelius OR mccain  AND  biden OR ANDERSON COOPER"
------ output ------
huckabee AND (jfkadlsfj fdsfldfj06329 OR reagan) AND OReilly   AND  (c
+linton OR sebelius OR mccain)  AND  (biden OR ANDERSON COOPER)
[download]