If you intend to do checks based on template tags you should hook on wp action. template_redirect will suffice too, but wp is earlier. This is when WP handles 404 itself.
To perform a 301 redirect use status_header( 301 );, wp_safe_redirect(); immediately followed by exit;
You could use a plugin handle these for you. It’s bit tricky to set-up if you are not that technical. Good luck.