This took me forever to figure out how to do, even when I'd figured it out some time before, so I thought I'd better document it here.
To get Pidgin to start on startup on Windows, go to Tools -> Plugins (yeah, that's right, it's a plugin). Find Windows Pidgin Options in the list, check it off, and click the Configure Plugin button. Now you should see the Start Pidgin on Windows Startup option.