How would you approach creating a "Mad Libs" style form in Drupal?

I'm intrigued by the idea in this article: "Mad Libs" Style Form Increases Conversion 25-40%. I'd like to test such a form in place of the registration form on a couple of Drupal sites; however, I'm not sure how to approach such an unorthodox form using Drupal's Form API.

Would it be practical to alter the existing user_register form using hook_form_alter? Is there a better way?

Ideally, I'd like to be able to token-ize each form field on an arbitrary form, then enter the "story" text with token IDs where the fields should appear. I'm not sure where in the form rendering process to do that though?

Interesting. You should build the form as one would normally build a drupal form, only with the fields in it. Your narrative would go in the template file that should be used to theme the form. Using template to theme forms is extremely easy. For example in your _theme hook, bind the form with a template file,

testmodule_theme()
{
  return array(
        "user_aboutme_form" => array(
            "arguments" => array( "form" => NULL ),
            'path' => $path_to_template_folder,
            "template" => "user-aboutme-form",
            )
);
}

Make sure you clear your theme cache in between. In your template file, you'll get the entire form array, and you can render individual elements using drupal_render function. With custom styling you can get the same look and feel as on the above website. The only catch here is to make sure you render the root form element i.e. drupal_render($form) after you are done with rendering individual form elements, that would put in form token values in the form, otherwise the form won't work.