To use LINQ, as you have said, you need to have .NET 3.5. Just to confirm this, the Wikipedia page for LINQ says:
Language Integrated Query (LINQ,
pronounced "link") is a Microsoft .NET
Framework component that adds native
data querying capabilities to .NET
languages using a syntax reminiscent
of SQL. Many of the concepts that LINQ
has introduced were originally tested
in Microsoft's Cω research project.
LINQ was released as a part of .NET
Framework 3.5 on November 19, 2007.
Due to the fact that machines may have some of the previous versions of .NET already installed, you may find that this site, Smallest Dot NET by Scott Hanselman (Microsoft employee) is useful. It works out the smallest updates you need to get up to date (currently 3.5 SP1).
As for whether it is reasonable to expect it on the client's machine, I guess it depends upon what you're creating. My feelings are:
Small low cost applications = PERHAPS NOT YET
A tiny application sold at low cost, perhaps targeting 3.5 is a little early and likely to reduce the size of your audience because of the annoyance factor.
Large commercial applications, with installers = YES
If it is a large commercial application (your baseline specifications are already WInXP or newer running on .NET 2.0), I don't think the customer would care. Put the redistributable on the installer disk!
Remember that adopting any new technology should be done for a number of reasons. What is your need to use LINQ, is it something that would be tough to replicate? If LINQ gives you functionality you really need, your costs and timetable are likely to benefit from selecting it. Your company gain by being able to sell the product for less or increase their margins.
One final option, as pointed out by Nescio, if all you need is Linq to Objects (eg. you don't need Linq to SQL or Linq to XML) then LinqBridge may be an option.