I found that the Windows Search Service in Windows Server 2008 is a bit hard to discover. The Windows Search Service is actually burried as a Role Service under the File Services Role.
These are the steps to add and enable the Windows Search Service in Windows Server 2008:
1) Start Server Manager
2) Click on Roles in the left navigation pane
3) Select Add Role in the Roles Summary pane to the right
4) Select the File Services role and click Next
5) Select the Windows Search role service
Finish the wizard and now you should have the Windows Search service up and running.