How can I set a cookie and then redirect in PHP?

If you have human-readable urls or subfolders (like www.domain.com/path1/path2/), then you must set cookie path to / to work for all paths, not just current one.

if($form_submitted) {
    ...
    setcookie('type_id', $new_type_id, time() + 60*60*24*30, "https://stackoverflow.com/");
    header("Location: $url");
    exit;
}

From PHP manual:

The path on the server in which the
cookie will be available on. If set to
“https://stackoverflow.com/”, the cookie will be available
within the entire domain . If set to
‘/foo/’, the cookie will only be
available within the /foo/ directory
and all sub-directories such as
/foo/bar/ of domain . The default
value is the current directory that
the cookie is being set in.