Communication channels will depend vastly on the type of product you have and your target clients. You can consider a few of following strategies.
* Social Media
Most important ones (Twitter, Facebook) already mentioned here. If your product is some web application which is targeted directly to end users this channel may prove to be the most valuable. Just remember that once-in-a-quarter updates don't work. These streams have to be alive no matter if you have a software update to announce or not. Note: for big products or those addressed to big clients this channel won't work that well.
* Product/company blog
When we are on social media another popular strategy is a blog: either product-related or company-related. As an example of the former you can take Google Reader Blog as an example of the latter you can take TargetProcess blog. Also you can approach this one creatively - for example Eric Sink on his personal blog writes mostly on the stuff of his company. In this case, again, it will work better if your relationships with clients/potential clients are rather informal. I'm yet to see a good corporate blog out there.
* Auto-updates messages
This one assumes you have a good auto-update mechanism, but for web based solution somewhere in the cloud I take it for granted. After successful update you can display messages with description what has changed. Many people will dismiss it anyway, but some will read.
* Messages within application
You can put information about new features within the application. This is something Facebook sometimes does - you can see a box on the top of your stuff which for example says that privacy settings have been changed or that a new localized version of the site is available. If I remember correctly it hangs there unless users closes the box, so direct action i required to dismiss the message which raises the chance that the message will actually be read.
* Mailing list
* Trade shows/Conferences
As crazy as it might sound people actually do that. If you know places where you can meet your users go there, talk with them, tell them what has changed. Direct communication always is more convincing than communication through electronic tools.
* Viral marketing/Buzz/Advertising
You can consider a campaign to share news about your new features. It won't work with every update you do, but for major changes it can be a good idea. A good example of this strategy is what Google did with Google Wave, which is by the way already dead product. There was a lot of buzz and viral messages spread all over the world about new cool Google product and what Google basically was doing was unveiling some details about the product to sustain interest. Of course this can be made easier with completely new products than with a stream of update messages.