$new_user = array("mail" can be omitted, but the important one is the username.
'name' => $username,
'pass' => $password,
'mail' => $email,
'status' => true,
Once the data is filled, call user_save() to create the user.
$new_user_object = user_save(NULL, $new_user);The important part is to give the first parameter NULL, as we want to be creating new users.
Be sure to check "$new_user_object afterwards != FALSE" in case the registration process failed.
This code was checked and working with Drupal 6.x.