Apache redirection is done at the server level, not through WordPress. I would suggest either:
1) seeing if your hosting control panel offers a redirection feature. Some control panels like cPanel allow you to set up page redirection with either 301 or 302, through an easy-to-use graphical user interface (GUI)
2) editing your .htaccess file directly in a plain-text editor. That is where you can set your redirects to be either 301 (permanent) or 302 (temporary). There are a number of different syntaxes possible for redirects - the best thing is to look in your host's documentation to find out what the correct syntax is for your particular server.
For example, one popular syntax is:
Redirect 301 /oldpage http://example.com/newpage
Actually, I should ask first...when setting a 301, does the browser still check to see if the link is valid, then redirects it accordingly, or does it redirect it immediately?
The browser redirects automatically to the new page as specified in your redirect rule. It doesn't matter whether the old page still exists or not.