In theory it's pretty easy:
string paths = Directory.GetFiles(@"D:\Temp", "*.lnk", SearchOption.AllDirectories);
But that will almost certainly fail unless your app has full access privileges - which it is not likely to have.
In that case, read the root directory with Directory.GetDirectories, then read all of them with the above code in a
block, substituting each drirectory name for the fixed path I used. You can then ignore the exception that is thrown when you try to access the recycle bin!