How do I make my site "notice" things to index?
Here are a few things you should check:


On the Search settings page (located at admin/config/search/settings), make sure Node is checked (enabled) as an Active Search Module.
On admin/reports/status, verify when your cron job was last executed. And use the link 'run cron manually' on that page to manually trigger the cron job to be run.
Disable the "PHP Filter" module (used for nodes that use the "PHP Code" input format), to not get stuck because of some bad PHP code stored in a node. Because nodes containing PHP can cause problems with search indexing.
Clear the cache.
Check the Drupal log for possible errors related to it.


Some more excerpts from Search module: an internal site search system, related to Re-indexing:


Content-related actions on your site (creating, editing, or deleting content and comments) automatically cause affected content items to be marked for indexing or reindexing at the next cron run. When content is marked for reindexing, the previous content remains in the index until cron runs, at which time it is replaced by the new content.
Unlike content-related actions, actions related to the structure of your site do not cause affected content to be marked for reindexing. Examples of structure-related actions that affect content include deleting or editing taxonomy terms, enabling or disabling modules that add text to content (such as Taxonomy, Comment, and field-providing modules), and modifying the fields or display parameters of your content types. If you take one of these actions and you want to ensure that the search index is updated to reflect your changed site structure, you can mark all content for reindexing by clicking the "Re-index site" button on the Search settings page (administer >> site configuration >> search settings in Drupal 6, or administer >> configuration >> search and metadata >> search settings in Drupal 7).


If none of this helps, then you may also want to look at issue # 1715366 (which started in D7 ...) for other possible causes of your issue.

PS: what happens if you run the cron job, eg by triggering it from the admin screens?