The report from Hold Security says that 1.2 billion sets of credentials are in the possession of this party. I have a feeling that this report may be a hoax or a partial hoax due to grammatical errors ("while we getting our full service ready") and self-advertising of their electronic identity monitoring service. If it is true, how should I respond to this mass credential theft? The report recommends identity protection services but would it be enough?
The report is authenticated at Russian Hackers Amass Over a Billion Internet Passwords - NYTimes.com. But much remains unclear, and even the times didn't note the conflict-of-interest that Hold Security is setting up by speaking in scary but unspecific terms about this, and only offering their own paid services to help victims out, as you allude to.
I'm surprised that there is no discussion of the importance of properly salting and slowly hashing passwords before storing them in password databases, as discussed here at 'passwords' tag wiki. If a site does that, and the passwords are strong, a hacker couldn't learn the passwords just by downloading databases from the web site. They'd need to modify the web site authentication code and capture passwords interactively as users log in. They would thus only slowly get the passwords of active users, and that kind of attack on a site is much more likely to be noticed.
But of course many web applications don't follow even these basic practices, as discussed for example at cryptography - Looking for example of well-known app using unsalted hashes
End-users should use this and other reports of web site hacking to motivate them to be careful about which web sites they interact with, and to be smart about how they deal with passwords. Using web sites that support the use of a well-protected web sign-on service that requires two-factor authentication is better than working with a less-well-resourced web site that manages their own password database. See also techniques for dealing in a sane way with a large password portfolio at How to help users manage password portfolios based on risks of compromise? - Information Security Stack Exchange.
If you've re-used passwords for important sites on other sites, you could benefit from changing those passwords, e.g. if the important site is not vulnerable, but another one with the same password has been hacked. But since many of the sites with problems remain vulnerable, just changing your password now on one of those may not help much. And as noted in the password portfolio discussion, changing passwords for sites where you really don't have any information or assets at risk is far less important.
In the United States identity protection usually consists of getting notices when credit is taken out in your name or locking your credit profile by using a claim that your identity has already been compromised. Considering the legal limits mentioned below that seems to have little value to me but perhaps it would help you sleep at night.
Suggest you use the legal system to your advantage if you are in the United States and limit your available funds in any online debit account while using credit cards instead as it is easier not to pay an invalid bill than to get money back into an emptied account. Here they are limited in liability to fifty dollars if you are attacked reference link.
This is a problem for all of us and the folks that wish to trade with us as well (see Target's $148 million loss posted this week). Chip and Pin credit cards will be coming our way here in the United States in the next few years but nothing significant is going to change on the threat front soon so learn to live with it and understand your legal rights.