the different version run side by side, so yes they need to install 3.5 even if they have already installed 4.0. But they will not interfere with each other, so your program will continue to use 3.5 unless you recompile it to target 4.0 (or configure it to use 4.0 - see edit below).
As was pointed out in this question microsoft has some guidance on this:
The .NET Framework 4 is highly compatible with applications that are built with earlier .NET Framework versions, except for some changes that were made to improve security, standards compliance, correctness, reliability, and performance.
The .NET Framework 4 does not automatically use its version of the common language runtime to run applications that are built with earlier versions of the .NET Framework. To run older applications with .NET Framework 4, you must compile your application with the target .NET Framework version specified in the properties for your project in Visual Studio, or you can specify the supported runtime with the <supportedRuntime>
Element in an application configuration file.
You can install .NET 3.5 and .NET 4.0 along side each other. Visual Studio 2010 also includes improved targetting support for .NET 3.5. ScottGu's blog talks about this in more detail.
EDIT:
As has been pointed out, you could modify the config of your app to tell it to use the 4.0 runtime if you want. this may or may not be ok depending on the bits of the framework you app uses. Safest it to install 3.5, but it is not strictly necessary, although you do have to make a change to your config to get it to work.