What to hook into to check a value before a post is published?

Try

function wpse46583_save($post_id,$post) {
     // verify this is not an auto save routine. 
     if ( defined('DOING_AUTOSAVE') && DOING_AUTOSAVE ) return;

     //You should check nonces and permissions here
      if ( !current_user_can( 'edit_page', $post_id )
           return;

     //Get category slugs associated with post
     $cats =get_the_category($post_id);

     if(empty($cats)){
        //No category assigned - do something here.
     }

     return;
}
add_action('save_post','wpse46583_save',10,2);