That's exactly how you do it. The PHP executes in a top-to-bottom fashion. Meaning, any code before the redirect will still happen. However, you cannot have any HTML output before a redirect, e.g.,
CODE
echo "My name is Fred";
header( ' Location: http://www.dreamincode.net ');
is illegal. That's because of how HTTP works. The header information is just that. The echoed string falls under the body of the document, and you cannot modify the header information after the body information has been sent (somebody correct me if I'm wrong).
Regardless, this:
CODE
$name = $_GET['thename'];
mysql_query("insert into mytable (name) values ('$name') ");
header("Location: http://www.hotmail.com");
is still valid and will insert data into a MySQL table before the redirect (provided my syntax is right for the insert statement

)