Posting this for future help for others:
The Search Results page was there - I did not know there was a Search Results page -- go to Admin, Pages - it will be there in the listing of pages you have added yourself, and the default DNN pages.
I viewed the settings of the Search Results page from the Admin, Pages area and it was allowed viewable by all users, so that was not it.
I then went and viewed the Search Results page from the Admin, Pages area, and it was a blank page - no modules were on it.
I then added the Search Results module to the page just like you would add any other module.
Search now works!
I had NO idea you had to populate the Search Results page manually with the Search Results module all by yourself.
DNN4 and earlier all did this for you.
Anyway - hope this helps some other users out there!