At "Meet the LINQ Team" session at TechEd, I got a few questions about LINQ to SQL and if it was possible to build a similar implementation. The answer is - absolutely you can. Take the soon-to-be released expression tree API documents, a few samples on the net and start cooking. What can you build a LINQ provider for? Any source of data worth querying. Who knows, it could be a smart fridge which tells you about the contents and perhaps down the road - your coffee machine.
The complexity of a provider depends on:1. What set of query operators you choose to implement; and2. Difference between the query operators and the target query language or API; and3. Level of optimization or tuning you want to do; and finally4. Availability of samples (yes, you guessed right. Our team members are working on this one in addition to the community at large)
Coffee machine aside, there are many providers already available. Most are based on May 2006 LINQ CTP but most can be upgraded to .NET Framework 3.5 without too much effort. Charlie's blog post and Oakleaf systems blog post have good starter lists.