Index solution for dynamic query
You can't make a single index that supports all of those optional parameters. You can make multiple indexes that do their best to support the most common combinations of parameters, but to support all possible combinations, the overhead is probably not worth it (and you'd have to measure the impact to the write portion of your workload - indexes aren't free).

My solution to the "customer can search in any way they please" problem is to create the kitchen sink procedure, which uses dynamic SQL to construct the where clause depending on the parameters provided. What this does is allow SQL Server to compile a separate plan for each combination of parameters, so that you don't have one massive query that tries to optimize for all scenarios but really can only optimize for very few. The basic approach would be:

CREATE PROCEDURE dbo.KitchenSink
  @param1 datatype = NULL,
  @param2 datatype = NULL
AS
BEGIN
  SET NOCOUNT ON;

  DECLARE @sql nvarchar(max) = N'SELECT ... FROM dbo.table 
    WHERE 1 = 1'

    + CASE WHEN @param1 IS NULL THEN N'' ELSE
        N' AND column1 = @param1' END

    + CASE WHEN @param2 IS NULL THEN N'' ELSE
        N' AND column2 = @param2' END

    ...
  ;

  EXEC sys.sp_executesql @sql, N'@param1 datatype, @param2 datatype, ...',
         @param1, @param2, ...;
END
GO


This will provide you with the opportunity to make the best use of any indexes that have key columns that align with combinations of supplied parameters. You will have to concede that some queries will just not perform well, but this should help minimize those cases.

Additional caveats:


You can use OPTION (RECOMPILE) inside the dynamic SQL to thwart parameter sniffing (for example, even when only lastname is supplied, the dynamic SQL alone won't help you generate the best plan every time, since a search for LIKE '%x%' will require a different plan than LIKE '[a-m]%').
You should use the optimize for ad hoc workloads setting (see here and here), so that SQL Server doesn't waste valuable plan cache space on potentially complex and large plans that are only used once.