I would only store it in the theme folder if I expected the favicon to change when I change the theme. Which I don’t.
A favicon is part of the total site identity, not a function of the CMS. What if you use non-WP software to run different parts of the site — e.g., a photo gallery, forum, or wiki (or all of the above)?
Put the favicon in the website root, and all software packages will have access to it, usually automatically (though you may have to remove hardcoded LINKs from individual themes).
(Edit) To clarify: If no LINK is specified, all modern web browsers (except Seamonkey, though an option exists to enable it) automatically look for a favicon at the root directory, i.e., example.com/favicon.ico. So there is no reason to add a LINK element, and good reason not to.
Furthermore, if the LINK element is malformed (has a typo, say) or the file located there is corrupt or in a format the browser doesn’t understand, the browser will go looking for /favicon.ico anyway, so not having a file there will result in 404 errors in your logs.
There is one case where a LINK is appropriate, and that is if you want different favicons for different pages of your site.