Como atualizar um banco de dados mysql sem recarregar a página

Você precisa do AJAX, como todo mundo já disse.

Como você nunca escreveu nenhum javascript, aqui está um guia para você.

Em vez de seu

<a href="add-item.php?itemid='.$itemId.'" > Add Item </a>

Escrever

<a onclick="addItemToUsersList('.$itemId.')" > Add </a>

Para AJAX, use jquery como Angelo sugeriu. Faça o download e adicione o seguinte

<script type="text/javascript" src="http://path/to/jquery-latest.min.js"></script>
<script type="text/javasript">
function addItemToUsersList(itemId)
{
  $.ajax({
    'url': 'path/to/add-item.php', 
    'type': 'GET',
    'dataType': 'json', 
    'data': {itemid: itemId}, 
    'success': function(data) 
    {
      if(data.status)
      {
        if(data.added)
        {
          $("span#success"+itemId).attr("innerHTML","Item added to your personal list");
        }
        else
        {
          $("span#success"+itemId).attr("innerHTML","This item is already on your list");
        }
      }
    },
    'beforeSend': function() 
    {
      $("span#success"+itemId).attr("innerHTML","Adding item to your bucketlist...");
    },
    'error': function(data) 
    {
      // this is what happens if the request fails.
      $("span#success"+itemId).attr("innerHTML","An error occureed");
    }
  });
}
</script>

E finalmente, em seu path/to/add-item.php file escreva o código para adicionar os itens. O parâmetro itemId estará disponível aqui como $_GET['itemId'] . Apenas retorne os valores de status apropriados usando json_encode.

if($bucketlist < 1) 
{
  mysql_query("INSERT INTO membersbuckets (memberbucketid, userid, bucketid, complete) VALUES ('', '$userid', '$_GET['itemId]', '0')");
  return json_encode(array("status" => true, "added" => true));
}
else
{
  return json_encode(array("status" => true, "added" => false));
}