Getting Custom post category from Form

Its pretty much what you already have, just add the following after $pid = wp_insert_post($new_post);:

#categories
  if( !empty ( $_POST ['categories'] ) ){
    update_post_meta ( $pid, "_testimonials_category", stripslashes ( $_POST ['categories'] ) );    
 }

I would probably advise you to change the name of this from categories though to something more relative, like testimonials_categories

Then you can use:

$chosen_testimonial_category = get_post_meta($pid,'_testimonials_category',true);

As for validation, check out jQuery.validate