How to semantically add heading to a list

Your first option is the good one. It's the least problematic one and you've already found the correct reasons why you couldn't use the other options.

By the way, your heading IS explicitly associated with the <ul> : it's right before the list! ;)

edit: Steve Faulkner, one of the editors of W3C HTML5 and 5.1 has sketched out a definition of an lt element. That's an unofficial draft that he'll discuss for HTML 5.2, nothing more yet.

a <div> is a logical division in your content, semantically this would be my first choice if I wanted to group the heading with the list:

<div class="mydiv">
    <h3>The heading</h3>
    <ul>
       <li>item</li>
       <li>item</li>
       <li>item</li>
    </ul>
</div>

then you can use the following css to style everything together as one unit

.mydiv{}
.mydiv h3{}
.mydiv ul{}
.mydiv ul li{}
etc...

In this case I would use a definition list as so:

<dl>
  <dt>Fruits I like:</dt>
  <dd>Apples</dd>
  <dd>Bananas</dd>
  <dd>Oranges</dd>
</dl>

As Felipe Alsacreations has already said, the first option is fine.

If you want to ensure that nothing below the list is interpreted as belonging to the heading, that's exactly what the HTML5 sectioning content elements are for. So, for instance you could do

<h2>About Fruits</h2>
<section>
  <h3>Fruits I Like:</h3>
  <ul>
    <li>Apples</li>
    <li>Bananas</li>
    <li>Oranges</li>
  </ul>
</section>
<!-- anything here is part of the "About Fruits" section but does not 
     belong to the "Fruits I Like" section. -->