How can I get my linked server working using Windows authentication?
Every machine in the chain from your desktop to the server you are calling has to be Kerberos enabled for the trust to advance past the first hop.  So, yes the server needs to trust the user for delegation.  

The "Login failed for user 'NT AUTHORITY\ANONYMOUS LOGON'" almost always indicates a delegation problem. 


Your Windows Account must have access to both ServerA and ServerB.
You must not have the setting "Account is sensitive and cannot be delegated."
Both ServerA and ServerB must have their own SPN registered.
The servers must be TCP/IP or named pipes connected.


The SQL Server Books Online article that offers some more detail is "Configuring Linked Servers for Delegation": 
http://msdn.microsoft.com/en-us/library/ms189580(v=sql.105).aspx