hook_form_alter and changing the taxonomy form input types in the Advanced Search

What I am trying to accomplish seems simple, but I haven't found a relevant solution.

I would like to change the input types of the taxonomy section of the Advanced Search from select to checkbox.

From what I've read, I need to create a checkboxnotselect.module and then use a hook_form_alter(), but what then?

I'm a complete nub at drupal, so forgive me if this is something I should already know.