<p>I understand the following elements :</p>

<ul>
<li>there is some sort of crawling (configured in central administration)</li>
<li>when the crawling is done, there is a slight delay, after which you can have your search results displayed.</li>
</ul>

<p>But, in a document library with publishing enabled, documents that are not published don't appear in search results. Is that normal ?</p>

All contents are crawled using the default content access account. Most of the time, this is a dedicated account, and SharePoint give it "Full Read" permissions.
Unfortunately, non approved items are not visible for "read users". So it will index the latest published version.
However, you can't really give more permissions to this user. If you do so, it will always index unpublished item, without indexing the latest publish version. So user without approvers permissions won't be able to search those items.