I run debian (wheezy) with kde-plasme-desktop installation (yes, this is the first time I try KDE). I checked this "Search and Launch" activity but it doesn't seem to be doing anything. As I saw from some videos it should show a search bar and find apps. Which libraries do I need to install to enable it? (or is there another setting that might be set off?)

this is how my desktop looks like in search and launch activity:

no search bar! nothing!

can you delete that activity and try creating a new one from the template

same result

strange
on my system it is provided (I think) by the KDE workspace package, can you reinstall it

does a new/different user have the same issue?

on my system these (I think) these are the required files, do you have them?
/usr/lib64/kde/plasma_engine_searchlaunch.so (if a 32bit it would be /usr/lib/...............)
/usr/share/kde/apps/plasma/services/searchlaunch.operations
/usr/share/kde/services/plasma-engine-searchlaunch.desktop