How can I see what visitors are searching for? Are visitor search terms stored somewhere in Drupal 6? I see a search_total table that might hold that info but the data in there looks kinda weird.

I'm using search module in core.
Unfortunately it's pretty limited.

View top search phrases (in Drupal 6.x):
yoursite.com/admin/reports/search

The data originates from the watchdog table, which means that how much data is provided depends on how far back your watchdog data goes (usually not far).

The Search Log module will provide more robust results. Or use Google Analytics, as the commenter above suggested.