How do I change html structure of menu (primary links for example) to my own?
I am assuming you are working with drupal6 and you have basic understanding of variables and arrays. Default html structure of the primary links is formed at different places in drupal. First if you start with the wrapping div id, in your theme's page.tpl.php file where you print $primary_links change it as the following example:

 &lt;div id="dk_one"&gt;
 &lt;?php print theme('links', $primary_links, array('class' =&gt; 'links primary-links dk_two')) ?&gt;
&lt;/div&gt;


In order to change what is in $primary_links use the following code in template.php file of your theme.

    function yourThemeName_links($links, $attributes = array('class' =&gt; 'links')) {
  $output = '';

  if (count($links) &gt; 0) {
    $output = '&lt;ul' . drupal_attributes($attributes) . '&gt;';

    $num_links = count($links);
    $i = 1;

    foreach ($links as $key =&gt; $link) {
      $class = $key;

      // Automatically add a class to each link and also to each LI
      if (isset($link['attributes']) &amp;&amp; isset($link['attributes']['class'])) {
        $link['attributes']['class'] .= 'dk_three ' . $key;
      }
      else {
        $link['attributes']['class'] = $key;
      }

      // Add first and last classes to the list of links to help out themers.
      $extra_class = '';
      if ($i == 1) {
        $extra_class .= 'first dk_four ';
      }
      if ($i == $num_links) {
        $extra_class .= 'last dk_five ';
      }
      $output .= '&lt;li ' . drupal_attributes(array('class' =&gt; $extra_class . $class)) . '&gt;';

      // Is the title HTML?
      $html = isset($link['html']) &amp;&amp; $link['html'];

      // Initialize fragment and query variables.
      $link['query'] = isset($link['query']) ? $link['query'] : NULL;
      $link['fragment'] = isset($link['fragment']) ? $link['fragment'] : NULL;

      if (isset($link['href'])) {
        $output .= l($link['title'], $link['href'], $link['attributes'], $link['query'], $link['fragment'], FALSE, $html);
      }
      else if ($link['title']) {
        //Some links are actually not links, but we wrap these in &lt;span&gt; for adding title and class attributes
        if (!$html) {
          $link['title'] = check_plain($link['title']);
        }
        $output .= '&lt;span' . drupal_attributes($link['attributes']) . '&gt;' . $link['title'] . '&lt;/span&gt;';
      }

      $i++;
      $output .= "&lt;/li&gt;\n";
    }

    $output .= '&lt;/ul&gt;';
  }

  return $output;
}


Clear your cache and you will see dk_one dk_two dk_four dk_five  div ids and classes in your html structure of your primary menu. Please let me know if it works for you.