Question:
How can I enable users to select "All" as the value of a query parameter?

Answer:
The simplest way is to modify your query to accept nulls and map "All" to null.

Step 1:  Start with a report that already has a parameterized query and Valid Values queries.

Step 2:  Edit your base query to account for nulls.
Whever you have something like this:
 ... AND Field = @Parameter ...
Replace it with this:
 ... AND (Field = @Parameter OR @Parameter is NULL) ...

Step 3:  Edit your Valid Values queries to insert an explicit "All" and separate ids from labels
For example, for this original query:
     SELECT name FROM productcategory
Change it to this:
     SELECT name as ID, name as Label FROM productcategory
     UNION
     SELECT Null as ID, 'All' as Label

Step 4:  Update the report parameters
Mark each parameter as nullable
Change the valid values settings to account for the new field names (if needed).

Step 5 (Optional):  Update Valid Values queries to account for nulls.
If you have hierarchical parameters, in some cases, you may want the dependent parameters to be independently selectable when the parent parameter's value is "All".  In this case, repeat step 2 for each of your Valid Values queries.  Note: Don't do this if you have extremely large numbers of possible values, as performance will suffer and your users wouldn't be able to nagivate an excessively long list anyhow.

Update