Creating a block that lists various posts for various categories I need to achieve something like this:

 

This is a block on a page. Stuff like U.S., Politics, World etc. are the categories (created by adding a custom vocabulary) and the sub-links are articles under those categories. I'm using Drupal 7.8 and have the Views module installed. 

Maybe I could write some PHP code and save as a block and then add that to a region. If so, which functions would I need?
Views are you friend. A View can also generate a Block. The sub-links are categories ordered by publishing date? Fairly easy.