What this does is prints out the heading of each category and lists only the posts in that category. Fill free to alter the loop to your needs, but keep the 'cat' => $cat_id, this is necessary for it to work. This doesn’t support pagination.

 $cats = get_categories(); foreach ($cats as $cat) {
    $cat_id= $cat->term_id;
    echo "<h2>".$cat->name."</h2>";

    query_posts( array('cat' => $cat_id, 'posts_per_page' => -1, 'post_type' => 'post'));
    if (have_posts()) : while (have_posts()) : the_post(); ?>

    <?php // stuff for the loop goes here... ?>
    <?php endwhile; endif; ?>
 <?php } ?>