The URL must be an absolute. See RFC 2616. But in most cases a relative URL will be accepted too.
PHP's "Location"-header still uses the HTTP 302-redirect code, but this is not the one you should use. You should consider either 301 (permanent redirect) or 303 (other).
Note: W3C mentions that the 303-header is incompatible with "many pre-HTTP/1.1 user agents. Currently used browsers are all HTTP/1.1 user agents. This is not true for many other user agents like spiders and robots.
HTTP Headers and the header() function in PHP
What the PHP manual says (read the link in the very bottom for where i got the answer)
What Wikipedia says (read the link in the very bottom for where i got the answer)
What the W3C says (read the link in the very bottom for where i got the answer)
You may use the alternative method of http_redirect($url); which needs the PECL package pecl to be installed.
5. Helper Functions
This function doesn't incorporate the 303 status code: