easycfm.com has entry level tutorials.
This book, http://forta.com/books/032166034X/, will help you get started.
For your specific questions, you can have a simple html form for your search page.
Whether you process the form on the same page or a different one doesn't really matter, but on that page, the form fields you submitted will now be cf variables in the form scope. You use the cfquery tag to send your sql to the db, and the cfoutput tag to display the results.
google and coldfusion play well together. If you search on cfquery, the adobe documentation will usually be the first offering.