How to add the logo in the fixed menu after a certain scrolling on the page?

In the site you left as an example, it might or may not have done 2 menus, usually, no, this does not happen, what happens is a class change, as in your code. It will not be different, one that will change to class :

What I did was create a div and add it, a img with its logo example:

<div class="logo-menu" >
   <img src="https://i.imgsafe.org/30c0a6d.jpg"alt="logo" style="height: 37px; width: 80px;" >
</div>

And it inserts its ul into another div , since the interaction between lists, divs and other elements can later generate problems. It looks like this:

<div class="lista-menu">
  <ul>
    <li><a href="http://seu-link">Início</a></li>
    <li><a href="http://seu-link">Sobre</a></li>
    <li><a href="http://seu-link">Contato</a></li>
    <li><a href="http://seu-link">Anuncie</a></li>
    <li><a href="http://seu-link">Parceria</a></li>
  </ul>
</div>

In HTML, that's just it ...

The main idea

You have an image, a logo, a pattern, a hidden one:

.menu .logo-menu{
   display: none;
}

But when it belongs to another class (in menu-fixo ), it can be viewed:

.menu-fixo .menu .logo-menu{
   display: inline-block; /* Algum display que possibilite a visualização */
}

The role of changing the class is only script . But let's make it clear that changes to the class will be necessary for everyone else to fit the image that will appear, which is what I'll do below.

Arranging ...

In css, I made some changes, all of them depending on the class that changes in its script , the class "fixed-menu":

.menu-fixo {
  z-index: 9999;
  position: fixed;
  top: 0;
  width: 880px;
  height: 37px;
}

.menu-fixo .menu {
  height: 37px;
}

.menu-fixo .menu ul {
  height: 37px;
  line-height: 37px; /* Centraliza o texto verticalmente */
  display: inline;
}

.menu-fixo .menu .logo-menu {
  display: inline-block;
  float: left;
}

The normal style, without the "fixed-menu" class, I have only a few considerations, but it's up to you:

.menu ul li {float: left; margin-top: 6px; padding: 6px;}

In the line above, when you put a float: left in li , it will not change much, since these are already left aligned by default.

Tip: And you gave margin-left of 228px . Are you sure this is necessary? If you want to right align, just use float: right to div that I created for li .

Complete Code

See if this is what you wanted:

jQuery("document").ready(function($) {
  var nav = $('.conteudo-menu');
  $(window).scroll(function() {
    if ($(this).scrollTop() > 500) {
      nav.addClass("menu-fixo");
    } else {
      nav.removeClass("menu-fixo");
    }
  });
});

.conteudo-menu {
  background: #ededed;
  font-family: Arial, Helvetica, sans- serif;
  font-size: 14px;
  border-bottom: 2px solid #ccc;
  border-top: 2px solid #ccc;
}

.menu-fixo {
  z-index: 9999;
  position: fixed;
  top: 0;
  width: 880px;
  height: 37px;
}

.menu-fixo .menu {
  height: 37px;
}

.menu-fixo .menu ul {
  height: 37px;
  line-height: 37px;
  position: relative;
  display: inline;
}

.menu-fixo .menu .logo-menu {
  display: inline-block;
  float: left;
}

.logo-menu {
  display: none;
}

.menu-fixo .menu .lista-menu {
  display: inline-block;
  float: left;
}
.menu { height: 60px;}
.menu ul { list-style: none; line-height: 30px;}
.menu ul li {display: inline-block; margin: 0 6px;}
.menu ul li:first-child { padding-left: 228px;}
.menu ul li a { color: #666; text-decoration: blink;}
.menu ul li a:hover { color: #777; text-decoration: underline;}

#pagina {
  height: 4000px;
  width: 100%;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><divclass="conteudo-menu">
  <div class="menu">
    <div class="logo-menu">
      <img src="https://i.imgsafe.org/30c0a6d.jpg"alt="logo" style="height: 37px; width: 80px;">
    </div>
    <div class="lista-menu">
      <ul>
        <li><a href="http://seu-link">Início</a></li>
        <li><a href="http://seu-link">Sobre</a></li>
        <li><a href="http://seu-link">Contato</a></li>
        <li><a href="http://seu-link">Anuncie</a></li>
        <li><a href="http://seu-link">Parceria</a></li>
      </ul>
    </div>
    <div class="clear"></div>
  </div>
</div>
<div id="pagina"></div>

Notice that in your% of% nothing has changed.