When you initiate a Loop, split it up like so:
<?php if (have_posts()) : ?>
<?php while (have_posts()) : the_post(); ?>
<!-- do stuff ... -->
<?php endwhile; ?>
<?php endif; ?>
Anything inside the if statement but outside the while statement will run if have_posts is true, but will not be Looped for each Post.
Also, it’s recommended that you use WP_Query, not query_posts – see here for more information. Be sure to reset the Loop after your query – it’s recommended here that wp_reset_postdata is the best option when using WP_Query.
So, in conclusion you should be writing something like this:
<?php
// Your arguments
$args = array(
'post_type' => 'stuff',
'taxonomy' => 'stuff-type',
'term' => 'new-stuff',
'orderby' => 'date',
'order' => 'DESC',
'posts_per_page' =>-1
);
// Let's get the query, using WP_Query
$loop = new WP_Query($args);
// Check if there are posts for our query
if ( $loop->have_posts() ) : ?>
<h2>New Stuff</h2>
<ul>
<?php
// Get looping
while ( $loop->have_posts() ) : $loop->the_post(); ?>
<li><a href="https://wordpress.stackexchange.com/questions/99859/<?php the_permalink(); ?>"><?php the_title(); ?></a></li>
<?php endwhile; ?>
</ul>
<?php endif; ?>
<?php wp_reset_postdata(); ?>
Hope that helps!