For future reference, here is what I did:

1. I had to make sure that I was using the full url path (http://mysite.com/...)
2. Here is the money line, thanks to citricguy: $search_string = url($search_string . urlencode($form_state['values']['search_value']));
3. $form_state['redirect'] = $search_string;

For future reference, here is what I did:

function my_search_form_submit($form, &$form_state) {

  if ($form_state['values']['area'] == 'cookbook') {
    $search_string = 'http://example.com/cookbook?recipe-search=';
  }
  elseif ($form_state['values']['area'] == 'blog') {
    $search_string = 'http://example.com/blog?blog-search=';
  }

  $search_string = url($search_string . urlencode($form_state['values']['search_value']));

  $form_state['redirect'] = $search_string;
}