Per the explanation here, a TOS is not required by law (but very useful in defining what is acceptable behavior, and I recommend having one), whereas a PP is mandatory for collecting any user information. While I've found a number of examples of how various sites have notified their users about changes to a PP (see here), I can't find anything about whether or not a site is legally obligated to do so. I suspect that larger, more established businesses (ones with big legal teams) are doing this more to protect themselves from potential litigation rather than following a specific law.
That said, I would recommend you treat your TOS as a legal contract, and act accordingly. If you have a clause in your TOS that says something like "We reserve to right to modify and/or correct this agreement and our Privacy Policy at any time; your continued use of the site implies agreement with the modified terms", then you're pretty well covered, though it's always good to notify your users for the sake of transparency. If you don't have a clause like that, I recommend, for the sake of protecting yourself, that you make your site require users to accept the new terms explicitly before using your site further, and that you include terms such as I mentioned. It's also good policy to explicitly state in the TOS how you will notify the users of changes (see the second link for different methods).
Last but not least, consider any legal requirements imposed upon your business by the type of business you are. My bank, for example, has a lot of legal requirements for how it handles my personal information that are the result of it being a financial institution, and not just from having a web site that I use. If you're a social networking site that relies on advertising for income, that's going to be a bit different than if you're an online retailer storing payment information. I strongly recommend you read through that first link I provided, as it discusses the legal requirements for dealing with personal information for all businesses, which are important even outside of the realm of the internet.