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