What?
There are a lot of articles & posts out there that cover the same topic, but as this took me the good part of an hour just to find out, I'm posting it here so I never have to look for it again.

A client changed their website domain address and wanted any person visiting the old domain to be redirected to the new domain.

Why?
I warned that a 301 site gets removed from the Google directory and true to form Google have removed it. Not sure why nobody believed me when I raised the alarm but hey-ho.

How?
I'm going to show you how to do this with a .htaccess file:
  1. Upload a text file to the root folder of the old domain's website
  2. Rename it as ".htaccess" (or modify the existing one)
  3. Add the code as per below.
  4. Save the change.
Different ways for different results, let's pretend I'm redirecting from myolddomain.com to mynewdomain.com: 
RewriteEngine On
RewriteRule ^(.*)$ http://www.mynewdomain.com/ [R=301]

# Redirects users from:
#       http://www.myolddomain.com -> 
#                       -> http://www.mynewdomain.com
#       http://www.myolddomain.com/category/folder/site.php -> 
#                       -> http://www.mynewdomain.com
#       http://www.myolddomain.com/anything -> 
#                       -> http://www.mynewdomain.com
Redirect domain but keep the rest of the URL: 
RewriteEngine on 
RewriteRule ^(.*)$ http://www.newdomain.com/$1 [R=301,L]

# Redirects users from:
#       http://www.myolddomain.com -> 
#                       -> http://www.mynewdomain.com
#       http://www.myolddomain.com/category/folder/site.php -> 
#                       -> http://www.mynewdomain.com/category/folder/site.php
#       http://www.myolddomain.com/anything -> 
#                       -> http://www.mynewdomain.com/anything