Here is a simple block of code that you can use to get the most recent post titles and permalinks to a certain number of the most recent posts in a certain category:

<ul>
<?php
    global $cat;
    $recentPosts = new WP_Query();
    $recentPosts->query('showposts=5&cat=389');
?>
<?php while ($recentPosts->have_posts()) : $recentPosts->the_post(); ?>
    <li><a href="<?php the_permalink() ?>" rel="bookmark"><?php the_title(); ?></a></li>
<?php endwhile; ?></ul>

Simply change the number of posts and the category id in the code above to get the number of posts and the category of posts that you want.

You can also check out my post on how to display a list of the titles of your most recent blog posts from several categories if you are looking for a way to get the most recent posts from several different categories.