I understand that it means an I/O function that could block indefinitely instead returns immediately. My question is, how does it do that? What happens if the function has to return immediately, but the I/O device is not available? Obviously it can't return immediately with the results of the I/O operation, because the operation hasn't had a chance to execute, so it has to do one of two things: either (1) return now with a result indicating failure, or (2) return control to the main program temporarily and perform the I/O operation concurrently with the main program, then return again when the I/O is completed. Which of these is it? What is the exact procedure followed? None of the sources I've been able to find clarify this point.
An I/O function delegates its operation to the OS Kernel. In general, these operations are asynchronous: the OS instructs a peripheral device to perform an operation, and eventually receives an interrupt from the device, indicating success or failure. In the meantime, the OS does many other things, including allowing user programs to run.
When an I/O operation is blocking for the user, then this means that the OS will not schedule CPU time for that user process until it has received the completion interrupt from the hardware. It then looks as if the function returned only after completion. In reality, it is ready to return immediately. It is only the OS that keeps the user process in a waiting state until the underlying hardware request has completed.
When an I/O operation is non blocking for the user, then the OS lets the user process continue immediately after it has initiated the corresponding hardware operation. It is then necessary to establish a notification mechanism for the user process to get notified when the operation completes. Details on how this is done vary from OS to OS.
Addendum:
In Posix, non-blocking means that if a request cannot be fulfilled immediately (e.g. you want to read something but data has not yet been received), then you get an error status. It is then up to you to re-issue the request later.