This is the loop I use in my search.php file (I believe it was taken from the basic Kubrick theme and altered):
<?php while (have_posts()) : the_post(); ?>
<div class="post">
<h3 id="post-<?php the_ID(); ?>"><a href="<?php the_permalink() ?>" rel="bookmark" title="Permanent Link to <?php the_title(); ?>"><?php the_title(); ?></a></h3>
<p class="postmetadata">Posted in <?php the_category(', ') ?> <small><?php edit_post_link('Edit', ''); ?></small></p>
</div>
<?php endwhile; ?>
<div class="navigation">
<div class="alignleft"><?php next_posts_link('« Previous Entries') ?></div>
<div class="alignright"><?php previous_posts_link('Next Entries »') ?></div>
</div>
<?php else : ?>
<p class="alert"><strong>Sorry, but your search for <em>'<?php echo wp_specialchars($s); ?>'</em> brought no results. You can check the lists below or try a different search.</strong></p>
<?php endif; ?>
This is the part of it that returns the title:
<h3 id="post-<?php the_ID(); ?>"><a href="<?php the_permalink() ?>" rel="bookmark" title="Permanent Link to <?php the_title(); ?>"><?php the_title(); ?></a></h3>