How does lock work exactly?

The lock statement is translated by C# 3.0 to the following:

var temp = obj;

Monitor.Enter(temp);

try
{
    // body
}
finally
{
    Monitor.Exit(temp);
}

In C# 4.0 this has changed and it is now generated as follows:

bool lockWasTaken = false;
var temp = obj;
try
{
    Monitor.Enter(temp, ref lockWasTaken);
    // body
}
finally
{
    if (lockWasTaken)
    {
        Monitor.Exit(temp); 
    }
}

You can find more info about what Monitor.Enter does here. To quote MSDN:

Use Enter to acquire the Monitor on the object passed as the parameter. If another thread has executed an Enter on the object but has not yet executed the corresponding Exit, the current thread will block until the other thread releases the object. It is legal for the same thread to invoke Enter more than once without it blocking; however, an equal number of Exit calls must be invoked before other threads waiting on the object will unblock.

The Monitor.Enter method will wait infinitely; it will not time out.

Its simpler than you think.

According to Microsoft: The lock keyword ensures that one thread does not enter a critical section of code while another thread is in the critical section. If another thread tries to enter a locked code, it will wait, block, until the object is released.

The lock keyword calls Enter at the start of the block and Exit at the end of the block. lock keyword actually handles Monitor class at back end.

For example:

private static readonly Object obj = new Object();

lock (obj)
{
    // critical section
}

In the above code, first the thread enters a critical section, and then it will lock obj. When another thread tries to enter, it will also try to lock obj, which is already locked by the first thread. Second thread will have to wait for the first thread to release obj. When the first thread leaves, then another thread will lock obj and will enter the critical section.

No, they are not queued, they are sleeping

A lock statement of the form

lock (x) ... 

where x is an expression of a reference-type, is precisely equivalent to

var temp = x;
System.Threading.Monitor.Enter(temp); 
try { ... } 
finally { System.Threading.Monitor.Exit(temp); }

You just need to know that they are waiting to each other, and only one thread will enter to lock block, the others will wait...

Monitor is written fully in .net so it is enough fast, also look at class Monitor with reflector for more details