The Recent Posts plugin (one of the various ones, maybe this one: http://wordpress.org/extend/plugins/recent-posts-plugin/) may help, but you may need a plugin that allows multiple copies of itself if you’re going to use it as a widget in a dynamic sidebar.
Otherwise, it looks to me like they set up four divs with different categories and listed the first five in each, which you can do easily with some PHP and custom Loops, or just calling the plugin provided function four times with different parameters.
Hi there! While the Recent Posts plugin will surely do the trick, if you’d like to try something a little more eye-catching, you might consider the Featurific for WordPress (http://wordpress.org/extend/plugins/featurific-for-wordpress/) plugin.
I forgot to mention that while the default location for Featurific is in the main content area, you can manually insert the plugin into the sidebar as well. Check out the demo sites for some examples, and the FAQ for instructions.