Can this be done?

Fairly simple to create a query on a portal page. Turn on filtering for the fields you want to search on.

Can I slap onthere a "Search" TexBox or do I have to use UI Designer for a functionality like that?

You have to use the Portal Page Designer, not UI Designer. Then drag over a Data Query to the blank work area. Click the box for Filter and change to Yes. Click Custom under the properties, then under the General tab click the API builder, make sure you select an index.

When done, when you click on a line it will pop up a filter on the left of your screen.

We used .NET and did a cool page that basically has one search box that as an example you can put in
  "Fred HR11"   or "Smith HR11" or "555-11-2222 hr11" or "1234 hr11" 
and it will search employee data for matches.  If there is more than one match it displays a list, on the other had if there is just one match then it will jump straight to hr11 and pulls up the employee.  It also defautls to the last form used so putting in HR11(etc.) is often not needed.
 
Basically the pieces are
1.  A full text index on the relevent columns(slightly more complicated than that).
2.  A asp.net page with the search box.
3.  A custom file under portal that sort of acts like lawform
4.  A slight addition to the HR11 form so you can pass it parameters and have it do the inquiry.
5.  ...repeat steps 1..4 on other forms/data as needed.

Thanks Jay... I'm trying to save time for our web developers, that's why I tried to slap this together using Portal Page designer.

I'm faced with a different issue, where I query on SSN in my portal page. I need to only display the last 4 digits...

I used a formlet that had a Custom_hr11 form and put the formlet on the portal page. Now I don't want to display the full SSN and only want to display the last 4 digits. It this possible?

Just create a new text field, then use script to parse out the last four digits and display it instead of the normal SSN field. You can remove the SSN field from the form and replace it with this new field.

I think there is a new field in the HR applications for this purpose...it might be in 9.0.1 and some MSP for 9.0.0 apps, but I don't remember exactly.