You might want to look at the answer to this similar question here:
https://stackoverflow.com/questions/11329823/add-where-clauses-to-sql-dynamically-programmatically

We’ve found that a SPROC which takes in a bunch of optional parameters and implements the filter like this :

CREATE PROC MyProc (@optionalParam1 NVARCHAR(50)=NULL, @optionalParam2 INT=NULL)
AS 
...
SELECT field1, field2, ... FROM [Table]
WHERE 
  (@optionalParam1 IS NULL OR MyColumn1 = @optionalParam1)
  AND (@optionalParam2 IS NULL OR MyColumn2 = @optionalParam2)

will cache the first execution plan it is run with (e.g. @optionalParam1 = 'Hello World', @optionalParam2 = NULL) but then perform miserably if we pass it a different set of optional parameters (e.g. @optionalParam1 = NULL, @optionalParam2 = 42). (And obviously we want the performance of the cached plan, so WITH RECOMPILE is out)

The exception here is that if there is ALSO at least one MANDATORY filter on the query which is HIGHLY selective and properly indexed, in addition to the optional parameters, then the above PROC will perform fine.

However, if ALL the filters are optional, the rather awful truth is that parameterized dynamic sql actually performs better (unless you write N! different static PROCS for each permutation of optional parameters).

Dynamic SQL like the below will create and cache a different plan for each permutation of the Query parameters, but at least each plan will be ‘tailored’ to the specific query (it doesn’t matter whether it is a PROC or Adhoc SQL – as long as they are parameterized queries, they will be cached)

So hence my preference for :

DECLARE @SQL NVARCHAR(MAX)        

-- Mandatory / Static part of the Query here
SET @SQL = N'SELECT * FROM [table] WHERE 1 = 1'

IF @OptionalParam1 IS NOT NULL        
    BEGIN        
        SET @SQL = @SQL + N' AND MyColumn1 = @optionalParam1'    
    END        

IF @OptionalParam2 IS NOT NULL        
    BEGIN        
        SET @SQL = @SQL + N' AND MyColumn2 = @optionalParam2'    
    END        

EXEC sp_executesql @SQL,        
    N'@optionalParam1 NVARCHAR(50), 
      @optionalParam2 INT'
    ,@optionalParam1 = @optionalParam1
    ,@optionalParam2 = @optionalParam2

etc. It doesn’t matter if we pass in redundant parameters into sp_executesql – they are ignored.
It is worth noting that ORM’s like Linq2SQL and EF use parameterized dynamic sql in a similar way.

The awful 1 == 1 hack can also be avoided if you keep track of whether any predicates have yet been applied or not, and then conditionally apply the first AND only on the second and subsequent predicates. If there are no predicates at all, then WHERE disappears as well.

Note that despite the dynamic query, we are still parameterizing the filters, if present, so we have at least a first line of defence against SQL Injection attacks.

Start with whatever you think is easier to implement (I guess option 2). Then measure the performance for real world data. Only start optimizing when needed, not beforehand.

By the way, depending on how complex your search filters are, your task may not be easily solved without dynamic SQL. So even when you use a stored procedure, that most probably won’t increase performance, as you already suspecting. On the other hand, if it helps, there are several types of hints (see http://www.simple-talk.com/sql/performance/controlling-execution-plans-with-hints/) you can add to an SQL query, dynamic or not, to help SQL server to optimize its execution plan.