Have you tried re-indexing?
Navigate to System > Index Management in your admin and select the relevant indexes.
Select reindex from the select box in the top left of the table, hit enter.
Before this please make sure you have set the product up correctly: In Stock set? Qty more than 0? Enabled?
Hope this helps,