A typical scenario might use a single encryption key for many different messages. A simple strategy is to allocate 64 bits to a message counter and 64 bits to a block counter. For each encryption you can increment the message counter by one. The block counter starts at zero and increments for each block of the message.

Note that this imposes hard limits on both the number of encryptions you can perform with this key (2^64) and the number of blocks a message can contain (also 2^64). As long as we respect these limits, we're guaranteed never to reuse a nonce.

If we use a random 64-bit nonce in place of the message counter, the picture changes a little. Due to the birthday paradox, we can now expect a collision in around 2^32 encryptions, which is a little close for comfort.

Fortunately, we can tune the bit allocations based on the needs of the application. So a reasonable strategy might be to bump the random message nonce to (say) 96 bits and leave 32 for the block counter. This still allows individual messages of around 64GB.

Of course, parameters like these should be considered implementation details for 99% of application developers. The best thing to do is to use a high-level library like NaCl that makes reasonable choices and then abstracts them away.