Good and basic solution for search page
You are correct. You could perfectly accomplish this with Views. A simple guide, just for illustration purposes, since we don't have the specifics in your question:


Create a View
In the FILTER CRITERIA section, add the desired filters (make sure to check the "Expose this filter to visitors..." checkbox) by doing that, you are indicating that you want it to be visible in the search page, so your users can change them.
In the OTHER area, mark "Use ajax" as "Yes" to submit the form asynchronously.
In the EXPOSED FORM area, go to "Exposed Form Style" > "Settings" and check the 
"Autosubmit" checkbox (if you wish to automatically submit the form once an element is changed).


Additionally, you could use the Better Exposed Filters module for advanced cool stuff (E.g. hiding the "Send" button, showing filters as checkboxes, etc).