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.
Start Pidgin on Windows Startup
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.