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.
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.