Document Availability

When I create a new document, I immediately see a reference tag to it in the Documents folder; however, the users that I assign rights to do not see it immediately. If I forward the document as an attachment and they open it, then they immediately see it. I haven't yet figured out exactly how long it takes for them to see the document without the forwarding, but I do see it happening. I create the document and assign the users rights to it. It doesn't show up in their documents folder, nor does it show up in their Default Library search folder. I originally thought it might have to do with nightly indexing, but then I had a new document show up for a users about an hour after I created it, instead of the next day.

What triggers the other users being able to see a new document?