Yes you can use the same controller for two different VF Pages. In order to avoid running the constructor a second time ( if you are not committing DML prior to page transfer - such as search results and a second page rendering the results ) you will need in your method to search to set
setRedirect( false );
to your page reference method that performs your search. The second page will then be able to use all of the data that you have returned here. If you are committing data on page change but using the same controller - but want to use other methods within the controller - you can set parameters in your save/search method to an object
setRedirect( true );
in order to commit your changes ( especially if making a callout after this change - you will need to commit changes first ).
If using method 2 - you can gather the parameters from the header in your constructor or second page action method when the second page loads and use the headers to perform your search query on page load.
For searches only i would suggest simply using the first method and redirect to the second page with
setRedirect( false );
on the Page reference.
NOTE: Transient variables may not persist across to the new page. so any variables that you need to persist - do not use as transient.